Recall the following problems for which we do not know a polynomial time algorithm:
- Clique. Does a graph have a clique of size .
- Independent Set. Does a graph have an independent set of size .
- Vertex Cover. Does a graph have a vertex cover of size .
- Satisfiability. Given a boolean formula is there an assignment that satisfies .
- Hamiltonian Cycle. Does have a simple cycle containing all the vertices.
- TSP. Given a weighted complete graph find a hamiltonian cycle of minimum cost in .
- Integer Linear Programming. Does such that such that and .
Note that all the above problems are in the class NP. Recall that the class NP consists of all the languages such that there is a non-deterministic Turing machine accepts in polynomial time. That is there is a non deterministic TM such that for any string , accepts in time polynomial in . Note that the class P NP.
- The problem Independent Set polynomial time reduces to Clique. That is if we have a polynomial time algorithm for Clique, then we get a polynomial time algorithm for Independent set. This is because given , let denote its complement. Then observe that any independent set in is a clique in . Conversely, Clique also reduces to Independent set by the same reduction.
- The problem Vertex Cover reduces in polynomial time to Independent set. Given a graph and a number , call Independent set on and . Note that the complement of any vertex cover in is an independent set. Thus there is a vertex cover in of size if and only if has an independent set of size .
- The problem 3-SAT reduces Clique. Given a formula construct a graph with a vertex for every variable in every clause. Given a variable and in two different clauses if they are compatible. Then the formula is satisfiable if and only if has a clique of size , where is the number of clauses.