# why is $\Pi_2$ smaller than $NP\cap coNP$

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

• 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! – Mohsen Ghorbani 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}$$.

• Okay, thanks. So $A$ may not even belong to $NP \cap coNP$ at all, correct? – Adam G Jun 25 '20 at 15:31
• Right. Of course we don't know for sure – for all we, know, the polynomial hierarchy collapses to $\mathsf{P}$. – Yuval Filmus Jun 25 '20 at 16:25
• 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$. – nir shahar Jun 25 '20 at 18:27