in ${\ensuremath{{\Pi}_{2}^{P}}}$ [@EiterG95]. This shows ${\ensuremath{{\Pi}_{3}^{P}}}$-membership.

For the hardness we reduce the ${\ensuremath{{\Pi}_{3}^{P}}}$-complete problem of deciding whether QBFs of the form $\forall X\exists Y\forall Z\phi$ are true to the problem of super-coherence. Without loss of generality, we can consider $\phi$ to be in DNF and, indeed, $X\neq\emptyset$, $Y\neq \emptyset$, and $Z\neq\emptyset$. We also assume that each disjunct of $\phi$ contains at least one variable from $X$, one from $Y$ and one from $Z$. More precisely, we shall construct for each such QBF $\Phi$ a program $P_\Phi$ such that $\Phi$ is true if and only if $P_\Phi$ is super-coherent. Before showing how to actually construct $P_\Phi$ from $\Phi$ in polynomial time, we give the required properties for $P_\Phi$. We then show that for programs $P_\Phi$ satisfying these properties, the desired relation ($\Phi$ is true if and only if $P_\Phi$ is super-coherent) holds, and finally we provide the construction of $P_\Phi$.

\[def:red\] Let $\Phi = \forall X\exists Y\forall Z\phi$ be a QBF with $\phi$ in DNF. We call any program $P$ satisfying the following properties a *$\Phi$-reduction*:

1.  $P$ is given over atoms $U=X\cup Y\cup Z \cup 
    \overline{X} \cup 
    \overline{Y} \cup 
    \overline{Z} \cup  \{u,v,w\}$, where all atoms in sets $\overline{S}=\{\overline{s} \mid s\in 