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.

**Reductions**

- 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.

Advertisements