Quelltext der Seite Satz von Fagin

Der '''Satz von Fagin''' ist ein 1973 von [[Ronald Fagin]] bewiesener Satz aus der [[Deskriptive Komplexitätstheorie|deskriptiven Komplexitätstheorie]], der aussagt, dass die Menge aller mit Hilfe der existentiellen [[Prädikatenlogik zweiter Stufe]] beschreibbaren Sätze genau die Komplexitätsklasse [[NP (Komplexitätsklasse)|NP]] ist.

Die existentielle Prädikatenlogik zweiter Stufe enthält Sätze, bei denen über die Prädikate eines Satzes aus der [[Prädikatenlogik erster Stufe]] existenzquantifiziert wird.
Genauer handelt es sich um Sätze der Form
:<math>\exists X_1 \ldots \exists X_k\,\varphi(x_1,\ldots, x_m,X_1,\ldots, X_k)</math>
wobei der Ausdruck <math>\varphi(x_1,\ldots, x_m,X_1,\ldots, X_k)</math> nur Quantifizierungen über die Individuenvariablen <math>x_1,\ldots, x_m</math> aber keine Quantifizierungen über die Prädikatvariablen <math>X_1,\ldots, X_k</math> enthält.
Die Klasse NP ist die Klasse derjenigen Entscheidungsprobleme, die von einer [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] in [[Polynomialzeit]] entschieden werden können.
Das Bemerkenswerte an diesem Satz ist, dass er eine Komplexitätsklasse nur auf der Basis einer Logik charakterisiert, ohne dabei auf ein Berechnungsmodell wie [[Turingmaschine]]n zurückzugreifen. Damit begründete er die deskriptive Komplexitätstheorie.

Larry J. Stockmeyer verallgemeinerte das Ergebnis und zeigte, dass die [[Polynomialzeithierarchie]] durch die allgemeine Prädikatenlogik zweiter Stufe (mit Allquantoren) beschrieben wird.

== Literatur ==

* [http://www.almaden.ibm.com/cs/people/fagin/ R. Fagin]. [http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf Generalized First-Order Spectra and Polynomial-Time Recognizable Sets] (PDF; 2,0&nbsp;MB). ''Complexity of Computation'', ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27–41. 1974.
* {{Literatur
 | Autor= [[Neil Immerman]]
 | Titel= Descriptive Complexity
 | Verlag= Springer
 | Jahr= 1999
 | Seiten= 113–119
 | ISBN= 0-387-98600-6
}}
*{{Literatur
 | Autor= [[Heinz-Dieter Ebbinghaus]], [[Jörg Flum]]
 | Titel= Finite Model Theory
 | Verlag= Springer
 | Jahr= 1999
 | Seiten= 119–164
 | ISBN= 3-540-28787-6
}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Satz (Mathematik)|Fagin, Satz von]]