Added to Favorites

Related Searches

Definitions

Nearby Words

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.## Proof

## References

It was proven by Ronald Fagin in 1974. 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.

Immerman 1999 provides a detailed proof of the theorem. Essentially, we use second-order existential quantifiers to guess a computation tableau. For every timestep, we guess the finite state control's state, the contents of every tape cell, and which nondeterministic choice we must make. Verifying that each timestep follows from each previous timestep can then be done with a first-order formula.

- R. Fagin Generalized First-Order Spectra and Polynomial-Time Recognizable Sets Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27-41. 1974.
- Immerman, Neil (1999).
*Descriptive Complexity*. New York: Springer-Verlag. ISBN 0-387-98600-6.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday March 31, 2008 at 05:45:12 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday March 31, 2008 at 05:45:12 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.