<p>The answer for the revised question (revision 4 of the question) is no.  If a decision problem <i>L</i> is solvable in time O(<i>n</i><sup><i>k</i></sup>) by a ∑<sub><i>i</i></sub>P machine, then <i>L</i> can be solved in linear time by a Turing machine with the oracle for <i>L</i>, which is a ∑<sub><i>i</i>+1</sub>P machine.  Therefore, ∑<sub><i>i</i></sub>TIME[O(<i>n</i><sup><i>k</i></sup>)] ⊆ Σ<sub><i>i</i>+1</sub>TIME[O(<i>n</i>)].</p>

CC BY-SA 2.5
2011-02-14T02:06:44.863Z
No, this is not how the definition of $\Sigma_j TIME[t(n)]$ works. If $\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for all $j,k$, then $NP \neq coNP$. If $NP = coNP$ and $\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for every $j,k$, let $O(n^c)$ be the running time of some nondeterministic algorithm for Tautology. Then we have $NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$, where the first inclusion is by assumption and the second inclusion follows from a standard simulation argument. This is a contradiction.
Ryan Williams
CC BY-SA 2.5
2011-02-14T04:52:23.597Z
@Ryan: The definition I used is: L∈ΣiTIME[t(n)] iff there exist a language O∈Σ(i−1)P and a nondeterministic t(n)-time Turing machine with the oracle for O that recognizes L.  I thought that this is the standard definition, but I do not have any reference to back up my claim.  What is the definition you are using?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-15T01:23:20.753Z
The definition is: $L \in \Sigma_i TIME[t(n)]$ iff there is a linear time predicate $R(x,y_1,\ldots,y_i)$ such that $x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$ is true.
Ryan Williams
CC BY-SA 2.5
2011-02-15T01:26:28.307Z
@Ryan: Ok, I did not know that definition.  If that is what the asker wanted to ask, my answer does not apply.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-13T17:53:47.127Z
2011-02-13T17:53:47.127Z
Tsuyoshi Ito
<p>Yes. For example, the usual proofs of the time hierarchy theorem (by directly simulating arbitrary machines) can be used to show that for every $c \geq 1$, $\Sigma_c TIME[n^k]$ is not a subset of $\Pi_c TIME[n^{k-1}]$. The reason for switching from $\Sigma$ to $\Pi$ is that, in this diagonalization argument, we have to do the "opposite" of the machine we're simulating, so we have to run in universal mode when the simulating machine is in existential mode, and vice-versa.</p>

<p>You can also get a result like this without switching from $\Sigma$ to $\Pi$: for every $c \geq 1$, $\Sigma_c TIME[n^k]$ is not a subset of $\Sigma_c TIME[n^{k-1}]$. This can be done using the proof of the time hierarchy due to Zak (reference: "<a href="http://dx.doi.org/10.1016/0304-3975%2883%2990015-4">A Turing machine time hierarchy</a>", Theoretical Computer Science 26(3):327--333, 1983). For an explicit reference to this version of the time hierarchy theorem, see <a href="http://pages.cs.wisc.edu/~dieter/">Dieter van Melkebeek</a>'s "<a href="http://pages.cs.wisc.edu/~dieter/Research/sat-lb-survey.html">A Survey of Lower Bounds for Satisfiability and Related Problems</a>" (available on his home page).</p>

CC BY-SA 2.5
2011-02-15T16:36:37.690Z
This answer very clearly demonstrates the existence of a time hierarchy theorem for every distinct level of the hierarchy. This does not immediately indicate the presence of such a theorem for PH as a whole.
Joseph
CC BY-SA 2.5
2011-02-15T23:06:35.730Z
Your stronger question will be hard to resolve affirmatively; it would imply $LOGSPACE \neq NP$. Suppose there is a $c$ and a language $L$ in $\Sigma_c TIME[n^k]$ that is not in $\Sigma_d TIME[n^{k-1}]$ for every $d$. Then $LOGSPACE \neq NP$. This is because every language $L \in LOGSPACE$ is in $\Sigma_d TIME[n^2]$ for some $d$ depending on $L$ (by a Savitch-theorem-type argument). So if $LOGSPACE = NP$ then in fact every language in $\Sigma_c TIME[n^k]$ is in $\Sigma_d TIME[n^2]$ for *some* $d$, contradictory to what you want to show.
Ryan Williams
CC BY-SA 2.5
2011-02-13T16:28:06.903Z
2011-02-13T18:30:25.063Z
2011-02-13T18:30:25.063Z
Ryan Williams
<p>Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in $O(n^{k-1})$ in any level of the polynomial hierarchy?
In other words - does there exist a time hierarchy theorem for the polynomial hierarchy like there does for P and NP?
If there does - a reference would be great.</p>

<p>The difficulty I ran into is that the simulating machine, when simulating machines from all levels of the hierarchy, is not in any distinct level of the hierarchy. Which leads to a related question - what is the smallest class such a simulating machine belongs to? Is there any sense in defining a class with $O(n)$ alternations (or $O(\log n)$ / $O(\log \log n)$)?</p>

CC BY-SA 2.5
2011-02-15T17:05:28.323Z
Using a linear number of alternations gives you PSPACE, since Quantified Boolean Formula is PSPACE-complete.
Derrick Stolee
<cc.complexity-theory><reference-request><polynomial-hierarchy><time-hierarchy>
Is there a Time Hierarchy theorem for PH?
Joseph
# Is there a Time Hierarchy theorem for PH?

(Asked by: username_0 on 2011-02-13)

Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in $O(n^{k-1})$ in any level of the polynomial hierarchy?
In other words - does there exist a time hierarchy theorem for the polynomial hierarchy like there does for P and NP?
If there does - a reference would be great.

The difficulty I ran into is that the simulating machine, when simulating machines from all levels of the hierarchy, is not in any distinct level of the hierarchy. Which leads to a related question - what is the smallest class such a simulating machine belongs to? Is there any sense in defining a class with $O(n)$ alternations (or $O(\log n)$ / $O(\log \log n)$)?

**Tags:** cc.complexity-theory, reference-request, polynomial-hierarchy, time-hierarchy

> **Comments:**
> **username_1**: Using a linear number of alternations gives you PSPACE, since Quantified Boolean Formula is PSPACE-complete.  

---

## 2 answers

### Answer by username_3 on 2011-02-13. Score: 17 | Accepted answer

Yes. For example, the usual proofs of the time hierarchy theorem (by directly simulating arbitrary machines) can be used to show that for every $c \geq 1$, $\Sigma\_c TIME[n^k]$ is not a subset of $\Pi\_c TIME[n^{k-1}]$. The reason for switching from $\Sigma$ to $\Pi$ is that, in this diagonalization argument, we have to do the "opposite" of the machine we're simulating, so we have to run in universal mode when the simulating machine is in existential mode, and vice-versa.

You can also get a result like this without switching from $\Sigma$ to $\Pi$: for every $c \geq 1$, $\Sigma\_c TIME[n^k]$ is not a subset of $\Sigma\_c TIME[n^{k-1}]$. This can be done using the proof of the time hierarchy due to Zak (reference: "[A Turing machine time hierarchy](http://dx.doi.org/10.1016/0304-3975%2883%2990015-4)", Theoretical Computer Science 26(3):327--333, 1983). For an explicit reference to this version of the time hierarchy theorem, see [Dieter van Melkebeek](http://pages.cs.wisc.edu/~dieter/)'s "[A Survey of Lower Bounds for Satisfiability and Related Problems](http://pages.cs.wisc.edu/~dieter/Research/sat-lb-survey.html)" (available on his home page).

> **Comments:**
> **username_0**: This answer very clearly demonstrates the existence of a time hierarchy theorem for every distinct level of the hierarchy. This does not immediately indicate the presence of such a theorem for PH as a whole.  
> **username_3**: Your stronger question will be hard to resolve affirmatively; it would imply $LOGSPACE \neq NP$. Suppose there is a $c$ and a language $L$ in $\Sigma_c TIME[n^k]$ that is not in $\Sigma_d TIME[n^{k-1}]$ for every $d$. Then $LOGSPACE \neq NP$. This is because every language $L \in LOGSPACE$ is in $\Sigma_d TIME[n^2]$ for some $d$ depending on $L$ (by a Savitch-theorem-type argument). So if $LOGSPACE = NP$ then in fact every language in $\Sigma_c TIME[n^k]$ is in $\Sigma_d TIME[n^2]$ for *some* $d$, contradictory to what you want to show.  

---

### Answer by username_2 on 2011-02-13. Score: 3

The answer for the revised question (revision 4 of the question) is no. If a decision problem *L* is solvable in time O(*n**k*) by a ∑*i*P machine, then *L* can be solved in linear time by a Turing machine with the oracle for *L*, which is a ∑*i*+1P machine. Therefore, ∑*i*TIME[O(*n**k*)] ⊆ Σ*i*+1TIME[O(*n*)].

> **Comments:**
> **username_3**: No, this is not how the definition of $\Sigma_j TIME[t(n)]$ works. If $\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for all $j,k$, then $NP \neq coNP$. If $NP = coNP$ and $\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for every $j,k$, let $O(n^c)$ be the running time of some nondeterministic algorithm for Tautology. Then we have $NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$, where the first inclusion is by assumption and the second inclusion follows from a standard simulation argument. This is a contradiction.  
> **username_2**: @Ryan: The definition I used is: L∈ΣiTIME[t(n)] iff there exist a language O∈Σ(i−1)P and a nondeterministic t(n)-time Turing machine with the oracle for O that recognizes L.  I thought that this is the standard definition, but I do not have any reference to back up my claim.  What is the definition you are using?  
> **username_3**: The definition is: $L \in \Sigma_i TIME[t(n)]$ iff there is a linear time predicate $R(x,y_1,\ldots,y_i)$ such that $x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$ is true.  
> **username_2**: @Ryan: Ok, I did not know that definition.  If that is what the asker wanted to ask, my answer does not apply.  

---

