I have the problem

If $\overline{3SAT}\in BP\cdot NP$ then $PH=\Sigma_3^P$

To solve this I am using a result $BP\cdot NP\subset NP/poly$ which I can prove (not doing here). I have two solutions but in both case I am failing to give a final statement which kind of goes like this $x\in L \iff $ this, this, this is true ('this' means some conditions here)

To Show $PH=\Sigma_3^P$ it is enough to show $\Pi_3^P\subseteq \Sigma_3^P$

Proof-try 1: Take $\Pi_3^P-3SAT$. Hence $$\phi\in\Pi_3^P\iff \forall x\exists y\forall z\ \phi(x,y,z)=1$$ Now consider the language $$L'=\left\{ \langle \phi,y_2\rangle\mid \forall \langle x,z\rangle\ \neg \phi(x,y,z)=0 \right\}$$Since $L'\in coNP$ we have a polynomial time turning machine $M$ such that $M(\langle \phi,y\rangle)=\psi$ such that $\psi\in \overline{3SAT}$. Now since $\overline{3SAT}\in BP\cdot NP\subseteq NP/poly$ there exists a polynomial-sized circuit $C$ such that $$\psi\in \overline{3SAT}\iff \exists s \ C(\psi,s)=1$$Now $$ M(\langle \phi,y\rangle)\in\overline{3SAT}\iff \exists C\exists s \ C(M(\langle \phi,y\rangle),s)=1$$ Now as I said I am stuck what should be the final statement at the right side of the if and only if symbol in $$\phi \in \Pi_3^P-3SAT\iff$$

Proof-try 2: Similarly take $\Pi_3^P-3SAT$. Hence $$\phi\in\Pi_3^P\iff \forall x\exists y\forall z\ \phi(x,y,z)=1$$Now fix $y$ we get $\psi(\cdot, \cdot)=\phi(\cdot, y,\cdot)$ Now $$\neg \psi(\langle x,z\rangle)=0\ \forall \langle x,z\rangle$$Hence $\neg \psi\in\overline{3SAT}$. Similarly since $\overline{3SAT}\in BP\cdot NP\subseteq NP/poly$ there exists polynomial size nondeterministic circuit $C$. Hence $$\neg \psi \in \overline{3SAT}\iff \exists s\ C(\neg \psi, s)=1$$Here again I am having trouble forming the last final statement

What should I do in this case



Your Answer

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