Question

Show that the language $\mathbf{MAX}\mathbf{-}\mathbf{CLIQUE}$from problem 7.48 isin.${\mathbf{P}}^{\mathrm{SAT}}$

Short answer

It is known that every language in DP is polynomial time reducible to Z and DP is also in NP. Also,$MAX-CLIQUE$ isNP-complete. Hence, using this we can solve the above problem.

Step-by-step solution

Checking for the given facts from the problem 7.48 

In a graph Gclique is maximum of the size kif and only if it has kclique size and does not have$k+1$clique size.

The language$CLIQUE$ is in $NP$and also in$co-NP$

Continuing with the solution

It is known that every language in DP is polynomial time reducible to Z and DP is also in NP. Also,$MAX-CLIQUE$ isNP-complete. Hence, using this we can solve the above problem.

Since,$\mathbf{NP}\in {\mathbf{P}}^{\mathrm{SAT}}$and,$\mathbf{coNP}\in {\mathbf{P}}^{\mathrm{SAT}}$is$\mathbf{MAXCLIQUE}$in.${\mathbf{P}}^{\mathrm{SAT}}$

And ${\mathit{P}}^{\mathbf{S}\mathbf{A}\mathbf{T}}\mathbf{\in }\mathit{N}{\mathit{P}}^{\mathbf{S}\mathbf{A}\mathbf{T}}$which implies that $MAXCLIQUE$ is in.$N{P}^{SAT}$