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 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 théorème de Lynch et à des résultats de Grandjean.
On trouve une preuve de ce théorème dans le livre de complexité descriptive de Neil Immerman.
Exemples
modifier
Le problème de 3-coloration est dans NP et est décrit par le langage {G | il existe une 3-coloration des sommets de G telle deux sommets adjacentes ne soient pas de la même couleur}. Le théorème de Fagin dit qu'il est décrit par une formule de la logique du second ordre existentielle. En fait, il est décrit par la formule suivante : .
Par exemple, le graphe ci-contre est un modèle de cette formule car il est coloriable avec trois couleurs.
Démonstration
modifier
Bibliographie
modifier- (en) Ronald Fagin, « Generalized First-Order Spectra and Polynomial-Time Recognizable Sets », SIAM-AMS Proceedings, vol. 7 « Complexity of Computation », , p. 27-41 (lire en ligne, consulté le )
- (en) Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, , 268 p. (ISBN 0-387-98600-6, lire en ligne), p. 113-119
