In computational complexity theory, the theory of NP-completeness refers to five key ideas:
- If a polynomial time reduction can be done from one problem to another, any polynomial time algorithm for the second problem can be converted into a polynomial time algorithm for the first.
- Most apparently intractable problems belong to the class of NP decision problems (where the solution is either yes or no) that can be solved in polynomial time by a non-deterministic computer.
- One problem in NP, the satisfiability problem, allows for every other problem in NP to be polynomial reduced to it. If we can solve the satisfiability problem with a polynomial algorithm, then so can every problem in NP, and so too satisfiability must be intractable.
- Every other problem in NP also has this same property.
Problems are NP-complete if they have the same property as the satisfiability problem, i.e., that they have no solution in P. Whether NP-complete problems are intractable or not is a key open question in theoretical computer science. Solutions to NP-complete problems can be verified quickly, but are difficult to find quickly.
Practically
Many practical problems belong to the class of NP-complete problems. Since we can reduce all NP-complete problems to each other, we can in theory use a SAT-solver to solve any NPC problem. However, we lose structural information about the problem that might help us solve it more efficiently.
Proof of NP-completeness
if , then . proof is simple suppose we have a Turing machine that decides if in poly time then to determine the complement, we wrap that Turing machine in another one that outputs the inverse