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, the set of decision problems that can be reformulated as a binary function A(x, y) over strings such that

1. for a certain constant number c it holds that a string x is an element of the original decision problem if there is a string y with length smaller than |x|^c such that A(x, y),
2. the function A is decidable by a Turing machine in polynomial time.

An y value for a certain x such that A(x, y) holds is usually referred to as a certificate for x since it shows the membership of x to the original decision problem.

The importance of this class of decision problems is that it contains many interesting searching and optimization problems where we want to know if there exists a certain solution for a certain problem or whether there exists a better solution. Examples are the traveling salesman problem where we want to know if there is a shorter route that goes through all the nodes in a certain network and the satisfiability problem where we want to know if a certain formula in propositional logic with propositional variables is satisfiable or not. In both cases there is a certificate (a path that is indeed shorter, a truth assignment that makes the formula true) that is limited in size and for which we can decide in polynomial time whether it solves the problem.

Because of its importance there have been many efforts to come up with algorithms that decide the problems in NP in polynomial time. However, it seems that for some problems in NP we cannot come up with an essentially better algorithm than the one that simply tries all possible certificates until we find the right one. Whether this is really true or not is still one of the big open questions in computer science (see Complexity classes P and NP for an in-depth discussion). An important notion in this context is the set of NP-Complete decision problems, which is a subset of NP and might be informally described as those problems in NP for which it is very unlikely that there exists a polynomial algorithm; once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is going to be very hard to find.

In the 2002 paper PRIMES in P, Manindra Agrawal and students found a polynomial-time algorithm for the well-known NP problem of determining whether a number is prime. However, since this problem is not known to be NP-complete, it does not show that P=NP.

There is a simple logical characterization of NP: it contains precisely those languages expressible in second order logic restricted to exclude universal quantification over relations, functions, and subsets.