<p>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:</p>

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

<p>O = { $&lt;G,k&gt;$ : the size of largest clique in G is k }</p>

<p>D = { $&lt;G,k&gt;$ : there is a clique of size >= k in G  }</p>

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

<ul>
<li>Reduce instance of O to instance of D by using observation 1</li>
<li>Reduce instance of D obtained to instance of $\sigma_2^p$ complete problem P</li>
<li>Solve P using M</li>
</ul>

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

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

CC BY-SA 3.0
2012-05-18T03:33:44.633Z
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.
Alan Guo
CC BY-SA 3.0
2012-05-18T07:48:02.740Z
@AlanGuos D is an NP-Complete problem. Yes, we can use M directly as you have stated. Nice insight.
rizwanhudda
CC BY-SA 3.0
2012-05-17T23:20:57.547Z
2012-05-18T08:16:42.703Z
2012-05-18T08:16:42.703Z
rizwanhudda
<p>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 ?</p>

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

<cc.complexity-theory><complexity-classes><optimization><polynomial-hierarchy>
PH and Optimization Problems
Jeigh
# PH and Optimization Problems

(Asked by: username_0 on 2012-05-17)

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.

**Tags:** cc.complexity-theory, complexity-classes, optimization, polynomial-hierarchy


---

## 1 answers

### Answer by username_1 on 2012-05-17. Score: 0 | Accepted answer

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 = { $$ : the size of largest clique in G is k }

D = { $$ : 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:**
> **username_2**: 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.  
> **username_1**: @AlanGuos D is an NP-Complete problem. Yes, we can use M directly as you have stated. Nice insight.  

---

