Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thank you, that pretty much solves my problem. :) – Mike B. Nov 18 '11 at 11:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.