NP (complexity)
In
computational complexity theory,
NP ("non-deterministic polynomial-time") is the set of decision problems solvable in
polynomial time on a non-deterministic
Turing machine. Or, equivalently, YES answers are checkable in polynomial time on a deterministic Turing machine given the right information.
A language L belongs to NP if there exists a two input polynomial time algorithm A and a constant c such that
- L = {x in {0,1}* | ∃ certificate, y with |y| = O(xc) such that A(x,y) = 1}
Algorithm A verifies
L in polynomial time.
See also: Complexity classes P and NP and NP-Complete.