1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hint: there is a very simple way to construct a problem which is both NP-hard and coNP-hard. $\endgroup$
    – user114966
    Dec 5, 2020 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, 2020 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, 2020 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, 2020 at 16:14

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
12
  • $\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$ Dec 5, 2020 at 15:26
  • $\begingroup$ Right, thanks. Let me modify the proof. $\endgroup$ Dec 5, 2020 at 15:26
  • $\begingroup$ Indeed, this makes it a bit harder to demystify the proof. $\endgroup$ Dec 5, 2020 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, 2020 at 16:42
  • $\begingroup$ Sometimes this kind of combination is denoted by $\oplus$. So $L = \mathsf{SAT}\oplus\mathsf{coSAT}$. $\endgroup$ Dec 5, 2020 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.