In
complexity theory,
NP is the set of
decision problems solvable in polynomial time on a nondeterministic
Turing machine. Or, equivalently, YES answers are checkable in polynomial time on a deterministic Turing machine. See
Complexity classes P and NP and
NP-Complete.