Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
NP is the class of decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input. Equivalently, these are decision problems where every "yes" instance has a proof of this fact, which has length polynomial in the size of the instance and can be verified deterministically in polynomial time.
One of the major open problems in computer science is whether P=NP. That is, whether deterministic polynomial time Turing machines have the same power as nondeterministic ones. Or, informally, whether being able to easily compute the answer to a problem (P) is the same as being able to easily verify an answer, in the sense given above. The Clay Mathematics Institute has offered a million-dollar prize for the resolution of this question.
For more information, see our reference question.
