From Wikipedia, the free encyclopedia.
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
- for a certain constant number c it holds that a string x is an elements of the original decision problem iff there is a string y with length smaller than |x|c such that A(x, y),
- the function A is decidable by a Turing machine in polynomial time.
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 travelling 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. Another example is the decision problem that contains all composite integers, where we want to know if there is a divisor greater than one, or not. In all these cases there is a certificate (a path that is indeed shorter, a truth assignment that makes the formula true, a divisor greater than one) 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.
