- Théorème de Fagin
-
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 (en) et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie d'une quantification existentielle sur les ensembles.
Ce résultat est remarquable, puisqu'il caractérise la classe NP sans avoir recours à un formalisme comme la machine de Turing.
La preuve de ce résultat fut établie en 1973 par Ronald Fagin (en) dans sa thèse de doctorat. Elle a été depuis reformulée et améliorée, notamment grâce au théorème de Lynch et à des résultats de Grandjean.
On peut trouver une preuve de ce théorème dans le livre de complexité descriptive (en) de Neil Immerman (en).
Références
- (en) R. Fagin, « Generalized First-Order Spectra and Polynomial-Time Recognizable Sets », dans SIAM-AMS Proceedings, R. Karp, vol. 7 « Complexity of Computation », 1974, p. 27-41 [texte intégral (page consultée le 1/07/2010)]
- (en) N. Immerman, Descriptive Complexity, New York, Springer-Verlag, 1999 (ISBN 0-387-98600-6), p. 113-119
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fagin's theorem » (voir la liste des auteurs)
Catégories :- Théorème de mathématiques
- Logique mathématique
- Calculabilité
Wikimedia Foundation. 2010.
