Fagin's theorem
Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der 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 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
known for
Wikipage redirect
Link from a Wikipage to another Wikipage
known for
primaryTopic
Fagin's theorem
Der Satz von Fagin ist ein 1973 von Ronald Fagin bewiesener Satz aus der 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 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
has abstract
Der Satz von Fagin ist ein 197 ...... llquantoren) beschrieben wird.
@de
Le théorème de Fagin est un ré ...... descriptive de Neil Immerman.
@fr
Teorema de Fagin é um resultad ...... leatório não determinísticas .
@pt
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
961,494,214
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
hypernym
comment
Der Satz von Fagin ist ein 197 ...... delt es sich um Sätze der Form
@de
Le théorème de Fagin est un ré ...... descriptive de Neil Immerman.
@fr
Teorema de Fagin é um resultad ...... al como uma máquina de Turing.
@pt
label
Fagin's theorem
@en
Satz von Fagin
@de
Teorema de Fagin
@pt
Théorème de Fagin
@fr