Editing Descriptive complexity theory (section)

== Non-deterministic polynomial time ==

=== Fagin's theorem ===
Ronald Fagin's 1974 proof that the complexity class NP was characterised exactly by those classes of structures axiomatizable in existential second-order logic was the starting point of descriptive complexity theory.<ref name=":1" /><ref>Immerman 1999, p. 115</ref>

Since the complement of an existential formula is a universal formula, it follows immediately that co-NP is characterized by universal second-order logic.<ref name=":1" />

SO, unrestricted second-order logic, is equal to the [[Polynomial hierarchy|Polynomial hierarchy PH]]. More precisely, we have the following generalisation of Fagin's theorem: The set of formulae in prenex normal form where existential and universal quantifiers of second order alternate ''k'' times characterise the ''k''th level of the polynomial hierarchy.<ref>Immerman 1999, p. 121</ref>

Unlike most other characterisations of complexity classes, Fagin's theorem and its generalisation do not presuppose a total ordering on the structures. This is because existential second-order logic is itself sufficiently expressive to refer to the possible total orders on a structure using second-order variables.<ref>Immerman 1999, p. 181</ref>