Question

A k-query oracle Turing machine is an oracle permitted to make at most k queries on each input. A k-query oracle Turing machine ‘M’ with an oracle for A is written${\mathrm{M}}^{\mathrm{A},\mathrm{k}}$ . Define ${\mathrm{P}}^{\mathrm{A},\mathrm{k}}$to be the collection of languages that are decidable by polynomial time k-query oracle Turing machines with an oracle for ‘A’.

1. Show that$\mathrm{NP}\cup \mathrm{coNP}\subseteq {\mathrm{P}}^{\mathrm{SAT},1}$
2. Assume that . Show that$\mathrm{NP}\cup \mathrm{coNP}\not\subset P^{\mathrm{SAT},1}$ .

Short answer

1. Using poly-time above problem can be solved i.e., by proving that union of the NP and coNP can be decided in polynomial time by using the oracle of the SAT problem, which implies that $NP\cup coNP\subseteq P^{SAT,1}$
2. The second part of the problem is also solved by using poly-time i.e, by proving that union of the NP and coNP can be decided in polynomial time by using the oracle of the SAT problem, which implies that $NP\cup coNP\subseteq P^{SAT,1}$

Step-by-step solution

Using poly-time

As we know, the oracle problem SAT is basically the NP-complete problem, and the NP language is basically encoded in the polynomial time SAT.

And WKT, $L\subseteq NP$and also, $P^{A,k}\in NP$ which implies that L and $P^{A,k}\in NP$,it can be reduced in Poly-time by the oracle problem SAT.

Therefore,$NP\subseteq P^{SAT}$

Similarly, even $\neg L\left(\in NP\subseteq P^{SAT}\right)$can be reduced in Poly-time by the oracle problem SAT.

Hence,$coNP\subseteq P^{SAT}$

As it is known that for each and every NP-complete problem there is coNP-complete problem. Now, suppose, coNP & NP are equal then in that case the polynomial collapsed to either NP or coNP.

But it is shown earlier that $NP\subseteq P^{SAT}$and$coNP\subseteq P^{SAT}$ .

Here, union operation is done between NP and coNP and the output is in either “yes” or “no” and hence, union is computed in the polynomial time.

Thus,$NP\cup coNP\subseteq P^{SAT,1}$

Proving the second part of the problem

As we know that the oracle problem SAT is basically the NP-complete problem and NP language is basically encoded in the polynomial time SAT.

And WKT, $L\subseteq NP$and also, $P^{A,k}\in NP$ which implies that L and $P^{A,k}\in NP$ ,it can be reduced in Poly-time by the oracle problem SAT.

Therefore,$NP\subseteq P^{SAT}$

Similarly, even $\neg L\left(\in NP\subseteq P^{SAT}\right)$can be reduced in Poly-time by the oracle problem SAT.

Hence,$coNP\subseteq P^{SAT}$

As it is known that for each and every NP-complete problem there is coNP-complete problem. But in this case coNP and NP are not equal.

i.e., $NP\subseteq P^{SAT}$and $coNP\subseteq P^{SAT}$.

Hence, the union is not computed in the polynomial time.

Thus,$NP\cup coNP\not\subset P^{SAT,1}$