Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT} \}$. What is the smallest class that $A$ is known to belong to?

Apparently, the answer is $\Pi_2$, although I thought it was $NP \cap coNP$, since if we have a non-deterministic machine $M_1$ that decides $SAT$ and another non-deterministic machine $M_2$ that decides $\overline {SAT}$, then we can define a machine $M_3$ that on input $(\phi_1, \phi_2)$, runs $M_1$ on $\phi_1$ and $M_2$ on $\phi_2$, and only accepts if both machines return True. If the input does belong to $A$, then for some set of nondeterministic choices, we know $M_3$ will accept. If the input doesn't belong to $A$, then either $M_1$ or $M_2$ always return False, and so $M_3$ always rejects.

My first question is whether my explanation correctly shows $A \in NP \cap coNP$. More importantly though, why is $\Pi_2$ smaller than $NP\cap coNP$!?

  • $\begingroup$ You can't find nondeterministic $M_2$ that decides $\overline{SAT}$. For this purpose you should find a polynomial guess that shows there is no assignment for SAT, just one witness needed not all of them and you have no access to the other branches of nondeterministic machine! $\endgroup$ Jun 25 '20 at 14:18

You seem to be using the following definition of $\mathsf{NP} \cap \mathsf{coNP}$: it consists of all languages of the form $L_1 \cap L_2$, where $L_1 \in \mathsf{NP}$ and $L_2 \in \mathsf{coNP}$. However, in reality $\mathsf{NP} \cap \mathsf{coNP}$ consists of all languages $L$ such that $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$.

  • $\begingroup$ Okay, thanks. So $A$ may not even belong to $NP \cap coNP$ at all, correct? $\endgroup$
    – Adam G
    Jun 25 '20 at 15:31
  • $\begingroup$ Right. Of course we don't know for sure – for all we, know, the polynomial hierarchy collapses to $\mathsf{P}$. $\endgroup$ Jun 25 '20 at 16:25
  • 1
    $\begingroup$ The set of all languages $L$ where $L=L_1\bigcap L_2$ and $L_1\in NP,L_2\in coNP$ is called $DP$. It is sometimes confusing, but it is not $NP\bigcap coNP$. $\endgroup$
    – nir shahar
    Jun 25 '20 at 18:27

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.