Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

Question

It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.

This can easily be understood inductively using oracle machines. The question is - why can't we continue the inductive process beyond a constant level of alternations and prove $\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$ (aka $\mathbf{AP}=\mathbf{PSPACE}$)?

I am looking for an intuitive answer.

Answer 1

The proof for $\mathbf{P}=\mathbf{AltTime}(O(1))$ ($=\mathbf{PH}$) is an induction using $\mathbf{P}=\mathbf{NP}$. The induction shows that for any natural number $k$, $\mathbf{P}=\mathbf{AltTime}(k)$ (and $\mathbf{AltTime}(O(1))$ is just their union).

The induction does not work when the number of alternation can change with the input size (i.e. when the number of possible alternations of the machine is not a number but a function of the input size, i.e. we are not showing that an execution of the machine on a single input can be reduced to no alternation, we are showing that the executions of the machine on all inputs can be "uniformly" reduced to no alternation).

Let's look at a similar but simpler statement. We want to show that the identity function $id(n)=n$ eventually dominates all constant functions ($f \ll g$ iff for all but finitely many $n$ $f(n) \leq g(n)$). It can be proven say by induction. For all $k$, $k \ll n$ (i.e. $f_k \ll id$ where $f_k(n)=k$), but we don't have this for non-constant functions like $n^2$, $n^2 \not \ll n$.

Answer 2

Compare the polynomial hierarchy with the hierarchy for interactive proofs. If for some fixed k, you have k alternations in an interactive proof -- IP(k) -- the resulting complexity class has no more power than what you get with two alternations -- that is, IP(k) = IP(2) = AM (assuming k≥2). However, if you allow a polynomial number of alternations, you get the complexity class IP = PSPACE, which is believed to be much bigger than AM, a class is contained in Π₂P, at the second level of the polynomial hierarchy. So this phenomenon actually happens (although, not so far as we know, with the polynomial hierarchy).

This happens because the reduction which takes a problem of size n in IP(k) and turns it into a problem in IP(2) blows up the problem size, so that while for any specific IP(k) the problem remains polynomial-size, if you let k vary, the resulting reduction doesn't give problems that are polynomial in k.

Answer 3

Here is a little intuition concerning the gap between constant and unbounded alternations: a polynomial operation repeated a constant number of times is polynomial, but repeated a polynomial number of times can be exponential. For example, take multiplication repeated on itself:

v = 2
for(i=1 to n)
  v = v*v

The number of iterations is linear, and output is exponential. But if you fix n, it is polynomial on the size of initial value.

Answer 4

Below I expand a little bit on the point in Peter's answer by trying to carry out the quantifier removal for more than constant number of steps to see where it fails and if anything can be salvaged from such an attempt.

Let's try to amplify $\mathsf{P}=\mathsf{NP}$ for more than constant number times.

Assume that $\mathsf{P}=\mathsf{NP}$. Therefore there is polynomial time machine that solves Ext-Circuit-SAT (is there a satisfying extension for a given circuit and a partial assignment to its inputs?).

More formally, we have a polytime algorithm $A$ with polynomial running time $p(n)\in\rm{poly}(n)$ s.t.

Given a Boolean circuit $\varphi$, and a partial assignment $\tau$ to the inputs,
$A$ returns "yes" if there is an extension of $\tau$ that satisfies $\varphi$, and return "no" otherwise.

To go over constant times, we need to do the quantifier removal effectively. We can do this because the Cook-Levin theorem is a constructive theorem, in fact it gives a polynomial time algorithm $Cook$ s.t.

Given a DTM $M$ receiving two inputs, and three unary numbers $n$, $m$, and $t$,
$Cook(M, n, m, t)$ returns a Boolean circuit of size $O(t^2)$ that simulates $M$ on inputs of length $(n,m)$ for $t$ steps.

Let's try to use these to extend the argument for $\mathsf{P}=\mathsf{PH}$ to obtain an algorithm solving TQBF (actually TQBCircuit, i.e. Totally Quantified Boolean Circuit problem).

The idea of the algorithm is as follows: we repeatedly use $Cook$ on $A$ to remove the quantifiers from a given quantified circuit. There are linear number of quantifiers so we hope to get a polynomial time algorithm (we have an algorithm with polynomially many steps using the polynomial time subroutine $Cook$). At the end of this process of quantifier elimination we will have a quantifier-free circuit which can be evaluated in polynomial time (Circuit Value problem is in $\mathsf{P}$, let $CV$ be a polynomial time algorithm for computing the circuit value of a given circuit).

However we will see that this idea does not work (for the same reason pointed out by Peter).

• Let $\varphi$ be a quantified circuit, (initialized to the given quantified formula).
• Let $k$ the number of quantifiers in $\varphi$.

• For $i$ from $k$ to $1$ do

  • Let $\psi$ = $Qx_k \sigma(x_1,...,x_k)$ be the last quantifier and the quantifier-free part.

  • If $Q = "\exists"$,

    1. Compute $C = Cook(A, |\sigma|, |x_1|+...+|x_k-1|, p)$,
    2. Substitute the input bits with $\sigma$ in the circuit $C$,
    3. Replace $\psi$ with $C$ in $\varphi$.

  • If $Q = "\forall"$,

    1. Consider $\psi$ as $\lnot \exists x_k \lnot \sigma$,
    2. Compute $C = Cook(A, |\lnot \sigma|, |x_1|+...+|x_k-1|, p)$,
    3. Substitute the input bits with $\lnot \sigma$ in the circuit $C$,
    4. Replace $\psi$ with the $\lnot C$ in $\varphi$.
• Compute and return $CV(\varphi)$.

The resulting algorithm looks polynomial time: we have polynomial many steps, each step is polynomial time computable. However this is not correct, the algorithm is not polynomial time.

Using polynomial time subroutines in a polynomial time algorithm is polynomial time. The problem is that in general this does not need to be true if the values returned by the subroutines are not of polynomial size in the original input and we assume that we do assignments about the values returning from the subroutines. (In the TM model we have to read the output of any polynomial time subroutine bit by bit.) Here the size of the returned value from algorithm $Cook$ is increasing (can be a power of the size of the input given to it, the exact power depends on the running time of $A$ and is around $p^2(|input|)$, so since we know that $A$ cannot be less than linear time, $|output|$ is at least $|input|^2$).

The problem is similar to the simple code below:

• Given $x$,
• Let $n = |x|$,
• Let $y = x$,
• For $i$ from $1$ to $n$ do
  • Let $y = y^{|y|}$, (i.e. concatenation of $|y|$ copies of $y$)
• Return y

Each time we execute $y = y^{|y|}$ we square the size of $y$. After $n$ executions we will have a $y$ which is $x^{2^n}$ and has size $n2^n$, obviously not a polynomial in the size of the input.

Let's assume that we only consider quantified formulas with $k(n)$ quantifier alternations (where $n$ is the total size of the quantified formula).

Assume that $A$ runs in time $p$ (e.g. linear time which is not ruled out so far), and have maybe a more efficient $Cook$ algorithm outputting a smaller circuit of size $l(t)$ in place of $t^2$, then we get an algorithm for ExtCircuitSat that runs in time $(l\circ p)^{O(k)}(n)=\underbrace{l(p(l(p(\dots(l(p(n)))))))}_{O(k)\mbox{ compositions}}$. Even in the case that both $l$ and $p$ were linear (but with total coefficient $a\geq 2$) we would get an algorithm which runs in time $\Omega(n2^{k(n)})$ and if $k(n) = \Theta(n)$ it would be $\Omega(n2^n)$ similar to the brute-force algorithm (and even this was based on assuming Cook-Levin can be performed on algorithms resulting circuits of linear size in the running time of the algorithm).

Answer 5

I think this is because at each level of the PH, the number of alternations is a constant (i.e. independent of the input size), while in AP, the number of alternations can be unbounded (yet polynomial in the size of the input).