NP-COMPLETE

NP-complete - Problems are divided into two categories: those for which there exists an algorithm to solve it with polynomial time complexity , and those for which there is no such algorithm. We denote the former class of problems by P. There are problems for which no known algorithm exists that solves it in polynomial time, but there is also no proof that no such algorithm exists. Among these problems that are not known to be in P (or in ~P), there is a subclass of problems known as NP-complete: those for which either all are solvable in polynomial time, or none are. Formally, a problem is NP if there exists an algorithm with polynomial time complexity that can certify a solution. For example, it is not known whether there exists a polynomial algorithm to solve a system of Diophantine equations, Ax=b for x in Z^n (integer n-vectors). However, we can certify any trial x in polynomial time, just by checking that it is in Z^n, then multiplying by A to compare with b. A problem, p, is NP-complete if it is NP and for any problem in NP, there exists a polynomial time algorithm to reduce it to p. A fundamental member of the NP-complete class is the satisfiability problem . It is an open question whether P=NP, and most regard the NP-complete problems as having exponential time complexity. Further details are in the supplement, Introduction to Computational Complexity, as pdf or ps .