PH and Optimization Problems

Let machine M solves the $\Sigma_2^p$-complete problem. We can use this machine to solve any "NP-Hard" optimization problem (which includes MAX-CLIQUE and MIN-COLORING) in additional time polynomial in size of input as follows:

The solution is described for MAX-CLIQUE but the same idea works for any NP-Hard optimization problem. Let G = (V, E) and

O = { $<G,k>$ : the size of largest clique in G is k }

D = { $<G,k>$ : there is a clique of size >= k in G }

Observation 1: Problem of deciding language O can be solved by making $\log{|V|}$ calls to the machine that decides D [Using Binary search]

• Reduce instance of O to instance of D by using observation 1
• Reduce instance of D obtained to instance of $\sigma_2^p$ complete problem P
• Solve P using M

The reductions are all polynomial time, so its easy to see that if M works in polynomial time then we can compute MAX-CLIQUE using M with polynomial time overhead.

Using the above reduction we can also see that M is at least as powerful as the machine that solves NP-hard optimization problems.

Solved by user1 (100 )
May 17, 2012 at 23:20