# 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(x
^{c}) such that A(x,y) = 1}

Algorithm A verifies

*L* in polynomial time.

*See also*: Complexity classes P and NP and NP-Complete.