Fagin's theorem
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. It was proven by Ronald Fagin in 1973 in his doctoral thesis. The arity required by the second-order formula was improved (in one direction) in Lynch's theorem, and several results of Grandjean have provided tighter bounds on nondeterministic random-access machines.
known for
Wikipage disambiguates
Wikipage redirect
primaryTopic
Fagin's theorem
Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. It was proven by Ronald Fagin in 1973 in his doctoral thesis. The arity required by the second-order formula was improved (in one direction) in Lynch's theorem, and several results of Grandjean have provided tighter bounds on nondeterministic random-access machines.
has abstract
Der Satz von Fagin ist ein 197 ...... llquantoren) beschrieben wird.
@de
Fagin's theorem is a result in ...... nistic random-access machines.
@en
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
Wikipage revision ID
727,561,923
hypernym
comment
Der Satz von Fagin ist ein 197 ...... gen über die Prädikatvariablen
@de
Fagin's theorem is a result in ...... nistic random-access machines.
@en
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