| Property |
Value |
| 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. (fr)
- 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. (fr)
|
| dbo:isPartOf
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9148 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1974 (xsd:integer)
- 1983 (xsd:integer)
- 1991 (xsd:integer)
- 1999 (xsd:integer)
- 2017 (xsd:integer)
|
| prop-fr:consultéLe
| |
| prop-fr:doi
| |
| prop-fr:fr
|
- Victor Vianu (fr)
- Victor Vianu (fr)
|
| prop-fr:id
|
- Fagin 1974 (fr)
- Fagin 1974 (fr)
|
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:journal
|
- STOC '91 Proceedings of the twenty-third annual ACM symposium on Theory of Computing (fr)
- STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing (fr)
- STOC '91 Proceedings of the twenty-third annual ACM symposium on Theory of Computing (fr)
- STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing (fr)
|
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Neil Immerman (fr)
- Serge Abiteboul (fr)
- Neil Immerman (fr)
- Serge Abiteboul (fr)
|
| prop-fr:lieu
|
- New York (fr)
- New York (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mr
| |
| prop-fr:nom
| |
| prop-fr:numéroChapitre
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
| |
| prop-fr:passage
|
- 40 (xsd:integer)
- 209 (xsd:integer)
- 347 (xsd:integer)
|
| prop-fr:prénom
|
- Victor (fr)
- Martin (fr)
- Serge (fr)
- Neil (fr)
- Victor (fr)
- Martin (fr)
- Serge (fr)
- Neil (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:périodique
|
- Proc. SIAM-AMS Sympos. Appl. Math. (fr)
- Proc. SIAM-AMS Sympos. Appl. Math. (fr)
|
| prop-fr:texte
| |
| prop-fr:titre
|
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (fr)
- Descriptive Complexity (fr)
- Generic Computation and Its Complexity (fr)
- Languages Which Capture Complexity Classes (fr)
- Generalized First-Order Spectra and Polynomial-Time Recognizable Sets (fr)
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (fr)
- Descriptive Complexity (fr)
- Generic Computation and Its Complexity (fr)
- Languages Which Capture Complexity Classes (fr)
- Generalized First-Order Spectra and Polynomial-Time Recognizable Sets (fr)
|
| prop-fr:titreChapitre
|
- Descriptive complexity (fr)
- Descriptive complexity (fr)
|
| prop-fr:titreVolume
|
- Complexity of Computation (fr)
- Complexity of Computation (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Cambridge University Press (fr)
- Springer-Verlag (fr)
- Amer. Math. Soc. (fr)
- Cambridge University Press (fr)
- Springer-Verlag (fr)
- Amer. Math. Soc. (fr)
|
| dct:subject
| |
| 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. (fr)
- 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. (fr)
|
| rdfs:label
|
- Complexité descriptive (fr)
- Descriptive complexity theory (en)
- Deskriptive Komplexitätstheorie (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:domain
of | |
| is dbo:isPartOf
of | |
| is dbo:wikiPageWikiLink
of | |
| is prop-fr:champs
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
