# How can I prove that a specific structure $\Pi_2$ problem is $\Pi_2$-complete?

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.

• 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. – Emil Jeřábek supports Monica Jan 10 at 8:50
• Simultaneously cross-posted to cs.stackexchange.com/questions/119391 . Please don’t do that. – Emil Jeřábek supports Monica Jan 10 at 8:51
• 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$. – Emil Jeřábek supports Monica Jan 10 at 8:56