Theoretical Computer Science

PH and Optimization Problems

If we have a machine which can solve any problem in the second level of PH, can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or MIN-COLORING ?

I think that the answer is yes and that the power of this machine is strictly powerful than the one for solving the optimization version. However, I am not sure the differences between decision class and function class,i.e, PH is a class of decision problems but optimization problems are not.


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.

Comments (2)

  • +0 – I don't see the point of this sequence of reductions. Isn't D an NP-complete problem? In your explanation, it seems you can use M to directly solve O by existentially verifying that there is a clique of size k and universally verifying there does not exist a clique of size k+1. — May 18, 2012 at 03:33  
  • +0 – @AlanGuos D is an NP-Complete problem. Yes, we can use M directly as you have stated. Nice insight. — May 18, 2012 at 07:48