Fagin's theorem is a result in
descriptive complexity theory that states that the set of all properties expressible in existential
secondorder 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 1974 (strictly, in 1973 in his doctoral thesis). The
arity required by the secondorder formula was improved (in one direction) in
Lynch's theorem, and several results of
Grandjean have provided tighter bounds on nondeterministic
randomaccess machines.
Proof
Immerman 1999 provides a detailed proof of the theorem. Essentially, we use secondorder existential quantifiers to arbitrarily choose a
computation tableau. For every timestep, we arbitrarily choose 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
firstorder formula.
A key idea from the proof is that we can encode a linear order of length
n<sup>
k</sup> as a 2
kary relation
R on a universe
A of size
n. To achieve this, we choose a linear ordering
L of
A and then define
R to be the
lexicographical ordering of
ktuples from
A with respect to
L.
References
 . . Complexity of Computation, ed. R. Karp, SIAMAMS Proceedings 7, pp. 27–41. 1974.

Read More