NP (complexity)
[2][Note 1] The first definition is the basis for the abbreviation NP; "nondeterministic, polynomial time".
[5] The complexity class NP can be defined in terms of NTIME as follows: where
is the set of decision problems that can be solved by a nondeterministic Turing machine in
Alternatively, NP can be defined using deterministic Turing machines as verifiers.
A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that Many computer science problems are contained in NP, like decision versions of many search and optimization problems.
To answer whether some of the integers add to zero we can create an algorithm that obtains all the possible subsets.
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?".
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.
[2] Equivalent to the verifier-based definition is the following characterization: NP is the class of decision problems solvable by a nondeterministic Turing machine that runs in polynomial time.
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.
NP is closed under union, intersection, concatenation, Kleene star and reversal.
However, there remain a large number of problems in NP that defy such attempts, seeming to require super-polynomial time.
The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent.
The proof is described by many textbooks, for example, Sipser's Introduction to the Theory of Computation, section 7.3.
Conversely, suppose we have a non-deterministic TM called A accepting a given language L. At each of its polynomially many steps, the machine's computation tree branches in at most a finite number of directions.
NP is contained in PSPACE—to show this, it suffices to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial-time verifier.
NP is also contained in EXPTIME, since the same algorithm operates in exponential time.
co-NP contains those problems that have a simple proof for no instances, sometimes called counterexamples.
If we permit the verifier to be probabilistic (this, however, is not necessarily a BPP machine[6]), we get the class MA solvable using an Arthur–Merlin protocol with no communication from Arthur to Merlin.
In terms of descriptive complexity theory, NP corresponds precisely to the set of languages definable by existential second-order logic (Fagin's theorem).
A major result of complexity theory is that NP can be characterized as the problems solvable by probabilistically checkable proofs 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.
