Encyclopedia > F > Fagin's theorem
Fagin's theorem
Fagin's theorem is a result in descriptive complexity theory which 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 which does not invoke a model of computation such as a Turing machine.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)