1
$\begingroup$

We know that the satisfiability problem for a formula in the form of $\exists x_0 \forall x_1 \exists x_2 \ldots Q_i x_i . \phi(x_0, \ldots, x_i)$ is complete for $\Sigma_{i}^p$, where $Q_i$ is a quantifier $\exists$ iff $i \equiv 0 \mod 2$, $\forall$ otherwise, hence there are $i$ quantifier alternations. Similarly, a $\Pi_i^p$-complete satisfiability problem can be defined. Additionally, $\Sigma_{i}^p \subseteq \Pi_{i+1}^p$ and $\Pi_{i}^p \subseteq \Sigma_{i+1}^p$.

We also know that $\exists x . \phi(x) \equiv \phi(\top) \vee \phi(\bot)$, and $\forall x. \phi(x) \equiv \phi(\top) \wedge \phi(\bot)$. Moreover, the elimination of the first quantifier can be done in logarithmic space.

To my understanding, this is a reduction of a $\Sigma_{i+1}^p$-complete problem to a problem in $\Pi_{i}^p$, as it removes 1 quantifier alternation and is computable in logarithmic space. But that would conclude that $\Sigma_{i+1}^p \subseteq \Pi_{i}^p$ and $\Pi_{i+1}^p \subseteq \Sigma_{i}^p$, implying the collapse of $PH$. So:

Where am I wrong?

1 Answers 1

2

When $x_i$ are boolean variables, the problem you mentioned is not (known to be) $\Sigma_{i+1}$-complete. The usual complete problem for $\Sigma_k$ is this:

$\exists x_{1,1} x_{1,2} \dots x_{1,n_1} \forall x_{2,1} \dots x_{2,n_2} \dots Q x_{k,1} \dots x_{k,n_k} \phi(x_{1,1}, \dots, x_{k, n_k})$

which can written in your form, but then $x_i$ are vector variables, and their length can vary with input, therefore the method $\exists x \phi = \phi(\bot) \vee \phi(\top)$ requires exponential time and is not a reduction.

Let's see $k=1$: You are saying that the satisfability problem for one variable $\exists x_0 \phi(x_0)$, where $x_0$ is 0 or 1, is NP-complete yet can be solved in polynomial time, therefore $P=NP$.

The error is in NP-complete claim, satisfiability is easy to solve in polynomial time if number of variables is constant.