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.
