Editing NP (complexity) (section)

== Other characterizations ==
In terms of [[descriptive complexity theory]], NP corresponds precisely to the set of languages definable by existential [[second-order logic]] ([[Fagin's theorem]]).

NP can be seen as a very simple type of [[interactive proof system]], where the prover comes up with the proof certificate and the verifier is a deterministic polynomial-time machine that checks it. It is complete because the right proof string will make it accept if there is one, and it is sound because the verifier cannot accept if there is no acceptable proof string.

A major result of complexity theory is that NP can be characterized as the problems solvable by [[probabilistically checkable proof]]s where the verifier uses O(log ''n'') random bits and examines only a constant number of bits of the proof string (the class '''PCP'''(log ''n'', 1)). More informally, this means that the NP verifier described above can be replaced with one that just "spot-checks" a few places in the proof string, and using a limited number of coin flips can determine the correct answer with high probability. This allows several results about the hardness of [[approximation algorithm]]s to be proven.