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.


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – Alan Guo
    May 18, 2012 at 3:33
  • $\begingroup$ @AlanGuos D is an NP-Complete problem. Yes, we can use M directly as you have stated. Nice insight. $\endgroup$ May 18, 2012 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.