Editing NP (complexity) (section)

== Background ==
Many [[computer science]] problems are contained in NP, like decision versions of many [[search problem|search]] and optimization problems.

=== Verifier-based definition ===
In order to explain the verifier-based definition of NP, consider the [[subset sum problem]]:
Assume that we are given some [[integer]]s, {−7, −3, −2, 5, 8}, and we wish to know whether some of these integers sum up to zero. Here the answer is "yes", since the integers {−3, −2, 5} corresponds to the sum {{nowrap|(−3) + (−2) + 5 {{=}} 0.}} 

To answer whether some of the integers add to zero we can create an algorithm that obtains all the possible subsets. As the number of integers that we feed into the algorithm becomes larger, both the number of subsets and the computation time grows exponentially.

But notice that if we are given a particular subset, we can ''efficiently verify'' whether the subset sum is zero, by summing the integers of the subset. If the sum is zero, that subset is a ''proof'' or [[witness (mathematics)|witness]] for the answer is "yes". An algorithm that verifies whether a given subset has sum zero is a ''verifier''. Clearly, summing the integers of a subset can be done in polynomial time, and the subset sum problem is therefore in NP.

The above example can be generalized for any decision problem. Given any instance I of problem <math> \Pi </math> and witness W, if there exists a ''verifier'' V so that given the ordered pair (I,&nbsp;W) as input, V returns "yes" in polynomial time if the witness proves that the answer is "yes" or "no" in polynomial time otherwise, then <math> \Pi </math> is in NP.

The "no"-answer version of this problem is stated as: "given a finite set of integers, does every non-empty subset have a nonzero sum?". The verifier-based definition of NP does ''not'' require an efficient verifier for the "no"-answers. The class of problems with such verifiers for the "no"-answers is called co-NP. In fact, it is an open question whether all problems in NP also have verifiers for the "no"-answers and thus are in co-NP.

In some literature the verifier is called the "certifier", and the witness the "[[certificate (complexity)|certificate]]".<ref name = "kleinberg2006"/>

=== Machine-definition ===
Equivalent to the verifier-based definition is the following characterization: NP is the class of [[decision problem]]s solvable by a [[nondeterministic Turing machine]] that runs in [[polynomial time]]. That is to say, a decision problem <math> \Pi </math> is in NP whenever <math> \Pi </math> is recognized by some polynomial-time nondeterministic Turing machine <math> M </math> with an '''existential acceptance condition''', meaning that <math> w \in \Pi </math> if and only if some computation path of <math> M(w) </math> leads to an accepting state. This definition is equivalent to the verifier-based definition because a nondeterministic Turing machine could solve an NP problem in polynomial time by nondeterministically selecting a certificate and running the verifier on the certificate.  Similarly, if such a machine exists, then a polynomial time verifier can naturally be constructed from it.

In this light, we can define co-NP dually as the class of decision problems recognizable by polynomial-time nondeterministic Turing machines with an existential rejection condition.  Since an existential rejection condition is exactly the same thing as a '''universal acceptance condition''', we can understand the ''NP vs. co-NP'' question as asking whether the existential and universal acceptance conditions have the same expressive power for the class of polynomial-time nondeterministic Turing machines.