| Property |
Value |
| dbo:abstract
|
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. La preuve de ce résultat fut établie en 1973 par Ronald Fagin dans sa thèse de doctorat. Elle a été depuis reformulée et améliorée, notamment grâce au et à des résultats de Grandjean. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. La preuve de ce résultat fut établie en 1973 par Ronald Fagin dans sa thèse de doctorat. Elle a été depuis reformulée et améliorée, notamment grâce au et à des résultats de Grandjean. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
|
| dbo:isPartOf
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3007 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1974 (xsd:integer)
- 1999 (xsd:integer)
|
| prop-fr:consultéLe
| |
| prop-fr:isbn
| |
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Neil Immerman (fr)
- Neil Immerman (fr)
|
| prop-fr:lieu
|
- New York (fr)
- New York (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Immerman (fr)
- Fagin (fr)
- Immerman (fr)
- Fagin (fr)
|
| prop-fr:pages
| |
| prop-fr:pagesTotales
| |
| prop-fr:passage
| |
| prop-fr:prénom
|
- Ronald (fr)
- Neil (fr)
- Ronald (fr)
- Neil (fr)
|
| prop-fr:périodique
|
- SIAM-AMS Proceedings (fr)
- SIAM-AMS Proceedings (fr)
|
| prop-fr:titre
|
- Descriptive Complexity (fr)
- Generalized First-Order Spectra and Polynomial-Time Recognizable Sets (fr)
- Descriptive Complexity (fr)
- Generalized First-Order Spectra and Polynomial-Time Recognizable Sets (fr)
|
| prop-fr:titreVolume
|
- Complexity of Computation (fr)
- Complexity of Computation (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
- Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles. C'est le résultat fondateur de la complexité descriptive. Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à une notion de modèle de calcul comme la machine de Turing. On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman. (fr)
|
| rdfs:label
|
- Satz von Fagin (de)
- Théorème de Fagin (fr)
- Satz von Fagin (de)
- Théorème de Fagin (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageWikiLink
of | |
| is prop-fr:renomméPour
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
