This HTML5 document contains 112 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
n25http://people.cs.umass.edu/~immerman/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n23http://g.co/kg/m/
n22https://researcher.watson.ibm.com/researcher/files/us-fagin/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n5http://fr.dbpedia.org/resource/Modèle:
n21http://citeseerx.ist.psu.edu/viewdoc/
n24http://fr.dbpedia.org/resource/Fichier:
n10http://commons.wikimedia.org/wiki/Special:FilePath/
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n19http://people.cs.umass.edu/~immerman/pub/
n13http://people.cs.umass.edu/~immerman/book/
owlhttp://www.w3.org/2002/07/owl#
n20http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbpedia-jahttp://ja.dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Complexité_descriptive
rdfs:label
Deskriptive Komplexitätstheorie Complexité descriptive Descriptive complexity theory
rdfs:comment
En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin.
owl:sameAs
dbpedia-ja:記述計算量 wikidata:Q1200755 dbr:Descriptive_complexity_theory dbpedia-de:Deskriptive_Komplexitätstheorie n20:133142742 n23:04hqc8
dbo:wikiPageID
7542341
dbo:wikiPageRevisionID
183943370
dbo:wikiPageWikiLink
dbpedia-fr:Problème_de_décision dbpedia-fr:Mu-calcul dbpedia-fr:Théorie_des_modèles dbpedia-fr:Logique_mathématique dbpedia-fr:NP_(complexité) dbpedia-fr:Récursivement_énumérable dbpedia-fr:AC0 dbpedia-fr:Classe_de_complexité dbpedia-fr:EXPTIME dbpedia-fr:Calcul_des_prédicats dbpedia-fr:Bisimulation dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) category-fr:Théorie_des_modèles category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:ELEMENTARY_(complexité) dbpedia-fr:PSPACE dbpedia-fr:Logique_d'ordre_supérieur dbpedia-fr:Machine_de_Turing dbpedia-fr:P_(complexité) dbpedia-fr:Théorème_de_Fagin dbpedia-fr:Neil_Immerman dbpedia-fr:Hiérarchie_polynomiale dbpedia-fr:Coloration_de_graphe dbpedia-fr:NL_(complexité) dbpedia-fr:Serge_Abiteboul n24:Petersen_graph_3-coloring.svg dbpedia-fr:Informatique_théorique dbpedia-fr:Ronald_Fagin
dbo:wikiPageExternalLink
n13:descriptiveComplexity.html n21:download%3Fdoi=10.1.1.698.6420&rep=rep1&type=pdf n22:genspec.pdf n19:capture.pdf n25:descriptive_complexity.html
dbo:wikiPageLength
9148
dct:subject
category-fr:Théorie_de_la_complexité_des_algorithmes category-fr:Théorie_des_modèles
prop-fr:wikiPageUsesTemplate
n5:Article_détaillé n5:Ouvrage n5:, n5:Section_vide_ou_incomplète n5:Portail n5:Références n5:Article n5:Lien
prov:wasDerivedFrom
wikipedia-fr:Complexité_descriptive?oldid=183943370&ns=0
foaf:depiction
n10:Petersen_graph_3-coloring.svg
prop-fr:année
1983 1974 1999 1991 2017
prop-fr:consultéLe
2019-11-07
prop-fr:doi
10.1145
prop-fr:fr
Victor Vianu
prop-fr:id
Fagin 1974
prop-fr:isbn
978 0
prop-fr:journal
STOC '91 Proceedings of the twenty-third annual ACM symposium on Theory of Computing STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing
prop-fr:langue
en
prop-fr:lienAuteur
Serge Abiteboul Neil Immerman
prop-fr:lieu
New York
prop-fr:lireEnLigne
n19:capture.pdf n22:genspec.pdf n21:download%3Fdoi=10.1.1.698.6420&rep=rep1&type=pdf
prop-fr:nom
dbpedia-fr:Ronald_Fagin Grohe Immerman Abiteboul Vianu
prop-fr:pages
43
prop-fr:pagesTotales
554
prop-fr:passage
209 40 347
prop-fr:prénom
Victor Serge Neil Martin
prop-fr:présentationEnLigne
n13:descriptiveComplexity.html
prop-fr:périodique
Proc. SIAM-AMS Sympos. Appl. Math.
prop-fr:texte
Vianu
prop-fr:titre
Generalized First-Order Spectra and Polynomial-Time Recognizable Sets Generic Computation and Its Complexity Descriptive Complexity, Canonisation, and Definable Graph Structure Theory Languages Which Capture Complexity Classes Descriptive Complexity
prop-fr:titreChapitre
Descriptive complexity
prop-fr:titreVolume
Complexity of Computation
prop-fr:volume
VII
prop-fr:éditeur
Springer-Verlag Amer. Math. Soc. Cambridge University Press
prop-fr:numéroChapitre
I.3
prop-fr:mr
371622
dbo:thumbnail
n10:Petersen_graph_3-coloring.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Complexité_descriptive
dbo:abstract
En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin.
dbo:isPartOf
dbpedia-fr:Théorie_des_modèles