19
$\begingroup$

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)$)?

Improve this question
$\endgroup$
1
  • $\begingroup$ Using a linear number of alternations gives you PSPACE, since Quantified Boolean Formula is PSPACE-complete. $\endgroup$
    – Derrick Stolee
    Feb 15, 2011 at 17:05

2 Answers 2

Reset to default
17
$\begingroup$

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", Theoretical Computer Science 26(3):327--333, 1983). For an explicit reference to this version of the time hierarchy theorem, see Dieter van Melkebeek's "A Survey of Lower Bounds for Satisfiability and Related Problems" (available on his home page).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Joseph
    Feb 15, 2011 at 16:36
  • 4
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 15, 2011 at 23:06
3
$\begingroup$

The answer for the revised question (revision 4 of the question) is no. If a decision problem L is solvable in time O(nk) by a ∑iP 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, ∑iTIME[O(nk)] ⊆ Σi+1TIME[O(n)].

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 14, 2011 at 2:06
  • $\begingroup$ @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? $\endgroup$
    – Tsuyoshi Ito
    Feb 14, 2011 at 4:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 15, 2011 at 1:23
  • $\begingroup$ @Ryan: Ok, I did not know that definition. If that is what the asker wanted to ask, my answer does not apply. $\endgroup$
    – Tsuyoshi Ito
    Feb 15, 2011 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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