# k-query oracle Turing machine

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.

• Hint: there is a very simple way to construct a problem which is both NP-hard and coNP-hard. – user114966 Dec 5 '20 at 6:47
• So any PSPACE-complete problem like TQBF will work, since NP and coNP are in PSPACE so the languages inside reduce to it? – Macrophage Dec 5 '20 at 6:53
• 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. – user114966 Dec 5 '20 at 7:21
• Oh I see what you mean, that's kind of what I tried to do but didn't quite figure out. – 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.

• 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? – D. Ben Knoble Dec 5 '20 at 15:26
• Right, thanks. Let me modify the proof. – Yuval Filmus Dec 5 '20 at 15:26
• Indeed, this makes it a bit harder to demystify the proof. – Yuval Filmus Dec 5 '20 at 15:36
• 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? – Macrophage Dec 5 '20 at 16:42
• Sometimes this kind of combination is denoted by $\oplus$. So $L = \mathsf{SAT}\oplus\mathsf{coSAT}$. – Yuval Filmus Dec 5 '20 at 16:46