Théorème de Fagin

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 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Fagin de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Logique epistemique — Logique épistémique La logique épistémique est la logique de la connaissance d agents pris individuellement. Son nom vient du verbe grec epistémei qui signifie savoir, qui a aussi produit le mot épistémologie. Ses créateurs sont E. J. Lemmon and… …   Wikipédia en Français

  • Logique Épistémique — La logique épistémique est la logique de la connaissance d agents pris individuellement. Son nom vient du verbe grec epistémei qui signifie savoir, qui a aussi produit le mot épistémologie. Ses créateurs sont E. J. Lemmon and Jaakko Hintikka.… …   Wikipédia en Français

  • Logique épistémique — La logique épistémique est la logique de la connaissance d agents pris individuellement. Son nom est tiré du nom grec epistḗmē qui signifie connaissance (du verbe epístamai savoir ), d où vient aussi le mot épistémologie. Ses créateurs sont E. J …   Wikipédia en Français

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”