A k-query oracle Turing machine can query its oracle for at most $k$ times. How could I show that assuming $\text{NP} \not= \text{coNP}$, we have $\text{NP} \cup \text{coNP} \subsetneq \text{P}^{\text{SAT},1}$ (query only once)? I tried to show this strict inclusion directly or its counterexample but to no avail... There was such a question on this site, but the top vote isn't a direct answer. Could somebody provide me more insight into this again? Thanks!

More specifically, I wonder how should I think of these $k$-query machines from machines with unlimited number of queries. I can see that they should have limited computation power, but I'm not sure how to utilize that for the proof.

  • $\begingroup$ Hint: there is a very simple way to construct a problem which is both NP-hard and coNP-hard. $\endgroup$ – user114966 Dec 5 '20 at 6:47
  • $\begingroup$ So any PSPACE-complete problem like TQBF will work, since NP and coNP are in PSPACE so the languages inside reduce to it? $\endgroup$ – Macrophage Dec 5 '20 at 6:53
  • $\begingroup$ No, TQBF almost surely doesn't lie in $P^{SAT,1}$. What I mean is that given two complexity classes $C_1,C_2$ and languages $L_1,L_2$ such that $L_1$ is $C_1$-hard and $L_2$ is $C_2$-hard, you can construct a language which is both $C_1$-hard and $C_2$-hard. $\endgroup$ – user114966 Dec 5 '20 at 7:21
  • $\begingroup$ Oh I see what you mean, that's kind of what I tried to do but didn't quite figure out. $\endgroup$ – Macrophage Dec 5 '20 at 16:14

Let's try to show the contrapositive. Since $\mathsf{NP} \cup \mathsf{coNP} \subseteq \mathsf{P}^{\mathsf{SAT},1}$, the contrapositive states that if $\mathsf{P}^{\mathsf{SAT},1} \subseteq \mathsf{NP} \cup \mathsf{coNP}$ then $\mathsf{NP} = \mathsf{coNP}$. Let us assume, therefore, that every problem in $\mathsf{P}^{\mathsf{SAT},1}$ is both in $\mathsf{NP}$ and in $\mathsf{coNP}$. We would like to show that this implies that $\mathsf{NP} = \mathsf{coNP}$.

We can imagine that the argument will have the following structure:

  1. Come up with some language $L \in \mathsf{P}^{\mathsf{SAT},1}$.
  2. The assumption implies that $L \in \mathsf{NP}$ or $L \in \mathsf{coNP}$.
  3. Use these facts to say something about the relation between $\mathsf{NP}$ and $\mathsf{coNP}$.

Our goal is to show that $\mathsf{NP} = \mathsf{coNP}$, or equivalently $\mathsf{NP} \subseteq \mathsf{coNP}$. This, in turn, is equivalent to showing that $\mathsf{SAT} \in \mathsf{coNP}$. Considering the plan above, what we need is to find a language $L \in \mathsf{P}^{\mathsf{SAT},1}$ such that both $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$ imply $\mathsf{SAT} \in \mathsf{coNP}$.

We can take as $L$ the following language: $$ L = \{(x,0) : x \in \mathsf{SAT}\} \cup \{(x,1) : x \notin \mathsf{SAT}\}. $$ Details left to you.

  • $\begingroup$ Er, I’m not super familiar with complexity theory, but doesnt $$A \subseteq B \cup C$$ only imply that elements in A are in at least one of B or C, but not necessarily both? $\endgroup$ – D. Ben Knoble Dec 5 '20 at 15:26
  • $\begingroup$ Right, thanks. Let me modify the proof. $\endgroup$ – Yuval Filmus Dec 5 '20 at 15:26
  • $\begingroup$ Indeed, this makes it a bit harder to demystify the proof. $\endgroup$ – Yuval Filmus Dec 5 '20 at 15:36
  • $\begingroup$ That's an interesting language! I remembered using a similar trick to construct a language neither Turing recognizable nor co-Turing recognizable...Is there a name for this disjoint union trick, and how does it work in general? $\endgroup$ – Macrophage Dec 5 '20 at 16:42
  • $\begingroup$ Sometimes this kind of combination is denoted by $\oplus$. So $L = \mathsf{SAT}\oplus\mathsf{coSAT}$. $\endgroup$ – Yuval Filmus Dec 5 '20 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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