Nondeterministic Polynomial-Time
An “NP machine” is a nondeterministic polynomial-time Turing machine. Then NP is the class of decision problems solvable by an NP machine such that
- If the answer is “yes,” at least one computation path accepts.
- If the answer is “no,” all computation paths reject.
Equivalently, NP is the class of decision problems such that, if the answer is “yes,” then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is “no,” then the algorithm must declare invalid any purported proof that the answer is “yes.”
See the complexity zoo entry here and its complement class coNP here
Notable problems
- SAT is complete for NP — TODO citation
Known relationships
- If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.