Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?

  • $\begingroup$ What do you mean by $\Pi_1 \land \Pi_2$? $\{ (x_1, x_2) \mid x_1 \in \Pi_1 \land x_2 \in \Pi_2 \}$? $\endgroup$ – dkaeae Jul 12 '19 at 15:50
  • $\begingroup$ I'm not sure I understand. Do you mean then $\Pi_1 \cap \Pi_2$ (i.e., set intersection)? $\endgroup$ – dkaeae Jul 12 '19 at 16:07
  • $\begingroup$ Given two formulas $\phi_1$ and $\phi_2$ we have $\exists x:\phi_1(x)=1$ is in $NP$ and $\forall y:\phi_2(y)=0$ is in $coNP$. Where is $\{\exists x:\phi_1(x)=1\}\wedge\{\forall y:\phi_2(y)=0\}$? $\endgroup$ – T.... Jul 12 '19 at 16:09
  • 2
    $\begingroup$ No. As @dkaeae has explained, problems are sets of strings. $\endgroup$ – David Richerby Jul 12 '19 at 19:00
  • 2
    $\begingroup$ I think Ariel meant second level. $\endgroup$ – Yuval Filmus Jul 13 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.