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.
Many practical problems belong to the class of NP-complete problems.
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