1
$\begingroup$

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$!?

$\endgroup$
1
  • $\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$ Commented Jun 25, 2020 at 14:18

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Okay, thanks. So $A$ may not even belong to $NP \cap coNP$ at all, correct? $\endgroup$
    – Adam G
    Commented Jun 25, 2020 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$ Commented Jun 25, 2020 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
    Commented Jun 25, 2020 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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