The polynomial hierarchy problem is describled as following: $$\varphi_1:= \forall x_1\forall x_2\cdots \forall x_n\exists x_{n+1}\exists x_{n+2}\cdots\exists x_{n+m}~\bigwedge_{i=1}^n[f_i(x_{n+1},\cdots, x_{n+m})\leftrightarrow x_i]=1,$$ where $x_1,\cdots,x_{n+m}\in\{0,1\}$ are variables; $f_i:\{0,1\}^{m}\rightarrow\{0,1\},~i=1,\cdots,n$ are Boolean functions; $x\leftrightarrow y=(x\wedge y)\vee(\neg x\wedge\neg y)$; How can prove such kind of $\Pi_2$ satisfiability problem $\varphi_1$ is $\Pi_2$-complete.

  • $\begingroup$ If you substitute constants into a Boolean function, you still get a Boolean function. That is, the problem is $\Pi_2^P$-complete even if there are no $x_{n+m+1},\dots,x_{2n+m}$ variables at all. $\endgroup$ – Emil Jeřábek supports Monica Jan 10 at 8:50
  • $\begingroup$ Simultaneously cross-posted to cs.stackexchange.com/questions/119391 . Please don’t do that. $\endgroup$ – Emil Jeřábek supports Monica Jan 10 at 8:51
  • $\begingroup$ Anyway, this is a bizarre way how to specify the problem. The natural way to define $\Pi_2$-SAT is to determine the truth of $\forall x_1\,\dots\,\forall x_n\,\exists x_{n+1}\,\dots\,\exists x_{n+m}\,f(x_1,\dots,x_{n+m})=1$ for a Boolean function $f$. $\endgroup$ – Emil Jeřábek supports Monica Jan 10 at 8:56

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.