<p>Compare the polynomial hierarchy with the hierarchy for interactive proofs. If for some fixed <em>k</em>, you have <em>k</em> alternations in an interactive proof -- IP(<em>k</em>) -- the resulting complexity class has no more power than what you get with two alternations -- that is, IP(<em>k</em>) = IP(2) = AM (assuming <em>k</em>&ge;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 &Pi;<sub>2</sub>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). </p>

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

CC BY-SA 2.5
2011-03-10T15:40:33.010Z
2011-03-10T20:13:27.760Z
2011-03-10T20:13:27.760Z
Peter Shor 
<p>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:</p>

<pre><code>v = 2
for(i=1 to n)
  v = v*v
</code></pre>

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

CC BY-SA 2.5
2011-03-10T10:24:52.220Z
2011-03-10T10:24:52.220Z
Ludovic Patey
<p>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.</p>

<p>Let's try to amplify <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span> for more than constant number times.</p>

<p>Assume that <span class="math-container">$\mathsf{P}=\mathsf{NP}$</span>. 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?).</p>

<p>More formally, we have a polytime algorithm <span class="math-container">$A$</span> with polynomial running time <span class="math-container">$p(n)\in\rm{poly}(n)$</span> s.t.  </p>

<blockquote>
  <p>Given a Boolean circuit <span class="math-container">$\varphi$</span>, and a partial assignment <span class="math-container">$\tau$</span> to the inputs,<br>
  <span class="math-container">$A$</span> returns "yes" if there is an extension of <span class="math-container">$\tau$</span> that satisfies <span class="math-container">$\varphi$</span>, and 
  return "no" otherwise.</p>
</blockquote>

<p>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 <span class="math-container">$Cook$</span> s.t.</p>

<blockquote>
  <p>Given a DTM <span class="math-container">$M$</span> receiving two inputs, and three unary numbers <span class="math-container">$n$</span>, <span class="math-container">$m$</span>, and <span class="math-container">$t$</span>,<br>
  <span class="math-container">$Cook(M, n, m, t)$</span> returns a Boolean circuit of size <span class="math-container">$O(t^2)$</span> that 
  simulates <span class="math-container">$M$</span> on inputs of length <span class="math-container">$(n,m)$</span> for <span class="math-container">$t$</span> steps.</p>
</blockquote>

<p>Let's try to use these to extend the argument for <span class="math-container">$\mathsf{P}=\mathsf{PH}$</span> to obtain an algorithm solving TQBF (actually TQBCircuit, i.e. Totally Quantified Boolean Circuit problem).</p>

<p>The idea of the algorithm is as follows: we repeatedly use <span class="math-container">$Cook$</span> on <span class="math-container">$A$</span> 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 <span class="math-container">$Cook$</span>). 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 <span class="math-container">$\mathsf{P}$</span>, let <span class="math-container">$CV$</span> be a polynomial time algorithm for computing the circuit value of a given circuit).</p>

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

<ul>
<li>Let <span class="math-container">$\varphi$</span> be a quantified circuit, (initialized to the given quantified formula).</li>
<li>Let <span class="math-container">$k$</span> the number of quantifiers in <span class="math-container">$\varphi$</span>.</li>
<li><p>For <span class="math-container">$i$</span> from <span class="math-container">$k$</span> to <span class="math-container">$1$</span> do  </p>

<ul>
<li>Let <span class="math-container">$\psi$</span> = <span class="math-container">$Qx_k \sigma(x_1,...,x_k)$</span> be the last quantifier and the quantifier-free part.  </li>
<li><p>If <span class="math-container">$Q = "\exists"$</span>,  </p>

<ol>
<li>Compute <span class="math-container">$C = Cook(A, |\sigma|, |x_1|+...+|x_k-1|, p)$</span>,  </li>
<li>Substitute the input bits with <span class="math-container">$\sigma$</span> in the circuit <span class="math-container">$C$</span>,  </li>
<li>Replace <span class="math-container">$\psi$</span> with <span class="math-container">$C$</span> in <span class="math-container">$\varphi$</span>.  </li>
</ol></li>
<li><p>If <span class="math-container">$Q = "\forall"$</span>,  </p>

<ol>
<li>Consider <span class="math-container">$\psi$</span> as <span class="math-container">$\lnot \exists x_k \lnot \sigma$</span>,  </li>
<li>Compute <span class="math-container">$C = Cook(A, |\lnot \sigma|, |x_1|+...+|x_k-1|, p)$</span>,  </li>
<li>Substitute the input bits with <span class="math-container">$\lnot \sigma$</span> in the circuit <span class="math-container">$C$</span>,  </li>
<li>Replace <span class="math-container">$\psi$</span> with the <span class="math-container">$\lnot C$</span> in <span class="math-container">$\varphi$</span>.</li>
</ol></li>
</ul></li>
<li>Compute and return <span class="math-container">$CV(\varphi)$</span>.</li>
</ul>

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

<p>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 <span class="math-container">$Cook$</span> is increasing (can be a power of the size of the input given to it, the exact power depends on the running time of <span class="math-container">$A$</span> and is around <span class="math-container">$p^2(|input|)$</span>, so since we know that <span class="math-container">$A$</span> cannot be less than linear time, <span class="math-container">$|output|$</span> is at least <span class="math-container">$|input|^2$</span>).</p>

<p>The problem is similar to the simple code below:</p>

<ul>
<li>Given <span class="math-container">$x$</span>,</li>
<li>Let <span class="math-container">$n = |x|$</span>,</li>
<li>Let <span class="math-container">$y = x$</span>,</li>
<li>For <span class="math-container">$i$</span> from <span class="math-container">$1$</span> to <span class="math-container">$n$</span> do

<ul>
<li>Let <span class="math-container">$y = y^{|y|}$</span>, (i.e. concatenation of <span class="math-container">$|y|$</span> copies of <span class="math-container">$y$</span>)</li>
</ul></li>
<li>Return y</li>
</ul>

<p>Each time we execute <span class="math-container">$y = y^{|y|}$</span> we square the size of <span class="math-container">$y$</span>. After <span class="math-container">$n$</span> executions we will have a <span class="math-container">$y$</span> which is <span class="math-container">$x^{2^n}$</span> and has size <span class="math-container">$n2^n$</span>, obviously not a polynomial in the size of the input.</p>

<p>Let's assume that we only consider quantified formulas with <span class="math-container">$k(n)$</span> quantifier alternations (where <span class="math-container">$n$</span> is the total size of the quantified formula). </p>

<p>Assume that <span class="math-container">$A$</span> runs in time <span class="math-container">$p$</span> (e.g. linear time which is not ruled out so far), and have maybe a more efficient <span class="math-container">$Cook$</span> algorithm outputting a smaller circuit of size <span class="math-container">$l(t)$</span> in place of <span class="math-container">$t^2$</span>, then we get an algorithm for ExtCircuitSat that runs in time <span class="math-container">$(l\circ p)^{O(k)}(n)=\underbrace{l(p(l(p(\dots(l(p(n)))))))}_{O(k)\mbox{ compositions}}$</span>. Even in the case that both <span class="math-container">$l$</span> and <span class="math-container">$p$</span> were linear (but with total coefficient <span class="math-container">$a\geq 2$</span>) we would get an algorithm which runs in time <span class="math-container">$\Omega(n2^{k(n)})$</span> and if <span class="math-container">$k(n) = \Theta(n)$</span> it would be <span class="math-container">$\Omega(n2^n)$</span> 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). </p>

CC BY-SA 3.0
2012-12-01T03:12:35.037Z
I really like this answer!!
Tayfun Pay
CC BY-SA 4.0
2019-11-20T10:43:48.297Z
@kaveh What if $p(n)=2^{\Omega(n)}$ while $l(t)=O(t)$ then do we need at least double exponential time for  $NP^{NP^{NP}}$? Your argument seems to suggest that possibility while we know $PSPACE$ is in $EXP$ and so how to get the single exponential back?
Turbo
CC BY-SA 4.0
2012-11-30T06:34:30.020Z
2019-09-13T01:10:50.007Z
2019-09-13T01:10:50.007Z
Kaveh
<p>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).</p>

CC BY-SA 2.5
2011-03-10T09:32:16.453Z
2011-03-10T09:32:16.453Z
Sadeq Dousti
<p>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 <em>number</em> $k$, $\mathbf{P}=\mathbf{AltTime}(k)$ (and $\mathbf{AltTime}(O(1))$ is just their union). </p>

<p>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 <em>number</em> but a <em>function</em> 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).</p>

<p>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$.</p>

CC BY-SA 2.5
2011-03-10T10:42:51.817Z
2011-03-10T11:19:13.033Z
2011-03-10T11:19:13.033Z
Kaveh
<p>It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.</p>

<p>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}$)?</p>

<p>I am looking for an intuitive answer.</p>

CC BY-SA 2.5
2011-03-14T11:12:39.427Z
See also related questions http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np and http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph
András Salamon
CC BY-SA 3.0
2011-10-04T14:56:43.047Z
It is known that $\mathsf{NL} = \mathsf{coNL}$ but it is suspected that $\mathsf{AL}$ (i.e. $\mathsf{P}$) is not equal to $\mathsf{NL}$.
sdcvvc
CC BY-SA 3.0
2012-12-05T20:07:43.887Z
related: [What's wrong with this proof that NP=coNP implies NP=PSPACE](http://cstheory.stackexchange.com/questions/6876/whats-wrong-with-this-proof-that-np-co-np-implies-np-pspace)
Kaveh
<cc.complexity-theory><polynomial-hierarchy><intuition>
Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?
Joseph
# Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

(Asked by: username_0 on 2011-03-10)

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.

**Tags:** cc.complexity-theory, polynomial-hierarchy, intuition

> **Comments:**
> **username_1**: See also related questions http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-p-np and http://cstheory.stackexchange.com/questions/5463/can-one-amplify-p-np-beyond-p-ph  
> **username_2**: It is known that $\mathsf{NL} = \mathsf{coNL}$ but it is suspected that $\mathsf{AL}$ (i.e. $\mathsf{P}$) is not equal to $\mathsf{NL}$.  
> **username_3**: related: [What's wrong with this proof that NP=coNP implies NP=PSPACE](http://cstheory.stackexchange.com/questions/6876/whats-wrong-with-this-proof-that-np-co-np-implies-np-pspace)  

---

## 5 answers

### Answer by username_3 on 2011-03-10. Score: 33 | Accepted answer

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 by username_4 on 2011-03-10. Score: 22

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 Π2P, 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 by username_5 on 2011-03-10. Score: 12

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 by username_3 on 2012-11-30. Score: 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).

> **Comments:**
> **username_6**: I really like this answer!!  
> **username_7**: @kaveh What if $p(n)=2^{\Omega(n)}$ while $l(t)=O(t)$ then do we need at least double exponential time for  $NP^{NP^{NP}}$? Your argument seems to suggest that possibility while we know $PSPACE$ is in $EXP$ and so how to get the single exponential back?  

---

### Answer by username_8 on 2011-03-10. Score: 3

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).


---

