Take the 2-minute tour ×


Let C be a set of function (let say time-computable increasing function to avoid pathological cases). Let's call $\rm{ATIME}(C,j)$ the class of langages decided by a Turing Machine begining in existantial state, alternating at most $j-1$ times and whose time is bounded by a function $f\in C$.

Let suppose that $\rm{ATIME}(C,j)=\rm{ATIME}(C,j+1)$ then, can we prove that $\forall k>j \rm{ATIME}(C,j)=\rm{ATIME}(C,k)$ ? Or at least, what are the condition over $C$ ?

It is true if $C$ is the class of polynomials because $C$ is then closed under composition. I would have expected it to be true for every polynomially closed set (for example for the exponential hierarchy, a class like $C=\{2^{2^{\dots^{2^{n^{O(1)}}}}}\}$ for a bouned tower of 2.)

I guess and hope that some things are known about it, but I was not able to find any reference, neither my advisor could.

An equivalent way to ask the question in a finite model theory setting, is:

Let HO$^{r,f}_j$ be the class of formula of order $r$ with free variable of order up to $f$ and with $j$ alternations of quantification of order $r$ beginning with an existantial quantification.

If there exists $k>2$ such that HO$^{r,2}_j$=HO$^{r,f}_k$ then can we proove that $\forall l>j$ HO$^{r,2}_j$=HO$^{r,2}_l$ ?

share|improve this question
this question needs some serious editing: it's incoherent right now –  Suresh Venkat Aug 9 '10 at 17:44
If the class $C$ has a single function that grows fast enough, then as far as I can tell, it is possible to have zero alternations be as powerful as up to $k$, but for $k+1$ alternations to beat $k$. I suspect you weren't wanting to include such pathological examples: do you have a more precise formulation of your question? –  András Salamon Aug 9 '10 at 18:59
@Suresh, I corrected the latex (for some reason it does not let me put _{j+1}, so I changed for _{k} with k>j. @Salamon, what you state is true. By example, if C is the class of Elementary function, then alternation does not change the expressivity. I changed my question to add as a question: what are the condition over C for this theorem to be known. In particular, is it true for the class of Turing Machine that interest my current research (bounded tower of 2) And for finite model theory, it is a result by Turull-Toress and Heila that those classes are equal to those classes of TM. –  Arthur MILCHIOR Aug 9 '10 at 19:19
@Dorais, I added "descriptive-complexity" because it is also a descriptive complexity problem, I translated the question at the end, but this is a real question about class of (high-order) formulae. So I do not really understand why you removed the tag. (In fact, I found this question studying those classes of formulae before I thought of it as a Turing Machine question) –  Arthur MILCHIOR Aug 9 '10 at 23:17

1 Answer 1

Let suppose that $ATIME(C;j)=ATIME(C;j+1)$ then can we prove that $\forall~k>j$, $ATIME(C;j)=ATIME(C;k)$? Or at least, what are the condition over $C$?

Yes, when $C$ is the class of polynomial functions of $n$, or the class of linear functions of $n$. First, note that your $ATIME(C;j)$ is typically written as $\Sigma_j TIME[C(n)]$. I will use this notation as it is more standard. Moreover it distinguishes between the classes where the machine starts in a universal state instead of an existential one. The universal version is written as $\Pi_j TIME[C(n)]$.

Now, $\Sigma_{j+1} TIME[C(n)]=\Sigma_j TIME[C(n)]$ implies $\forall~k>j$, $\Sigma_k TIME[C(n)]=\Sigma_j TIME[C(n)]$, when $C(n)$ is the class of all polynomial functions of $n$, or the class of linear functions of $n$. In fact, you can get away with the weaker assumption $\Pi_j TIME[C(n)] = \Sigma_j TIME[C(n)]$ in place of $\Sigma_{j+1} TIME[C(n)]=\Sigma_j TIME[C(n)]$. This follows from standard stuff in the chapters on alternations and the polynomial hierarchy of any complexity theory book. (You probably are well aware of this, but other readers may not be. So please bear with me.) For example, one result you may see in a complexity course is $NP = coNP$ implies that the polynomial hierarchy collapses to $NP$. This is exactly the same as saying $\Pi_1 TIME[n^{O(1)}] = \Sigma_1 TIME[n^{O(1)}]$ implies $\bigcup_{k \geq 1} \Sigma_k TIME[n^{O(1)}] = \Sigma_1 TIME[n^{O(1)}]$, which is the case $j=1$ in your question.

For superpolynomial functions $C(n)$, one runs into trouble. Suppose $\Sigma_j TIME[2^{O(n)}] = \Sigma_{j+1} TIME[2^{O(n)}]$, and you want to show $\Sigma_{j+2}TIME[2^{O(n)}] \subseteq \Sigma_{j+1} TIME[2^{O(n)}]$. The usual way of doing this is to take a $\Sigma_{j+2}$ machine, and consider the language $L'$ of pairs ${(x,y)}$ with the property that, if I feed $x$ to the machine, and substitute the string $y$ in place of the guesses for the first existential mode, the remaining $\Pi_{j+1}$ computation accepts. $L'$ is in $\Pi_{j+1}$, and so you usually apply your assumption to conclude $L'$ is in $\Pi_j$, hence the whole computation is in $\Sigma_{j+1}$. But observe that this "remaining $\Pi_{j+1}$ computation" runs in polynomial time in the length of the input, since the string $y$ can be of length $2^{O(n)}$, and the remaining computation takes $2^{O(n)}$ time. So it appears you need an assumption about polynomial time alternating computation in order to get this collapse. If you apply $\Sigma_j TIME[2^{O(n)}] = \Sigma_{j+1} TIME[2^{O(n)}]$ you end up with a doubly-exponential time computation.

I don't think any alternative argument for this kind of collapse is known, which gives you what you want. If you find one, please tell me! It may have applications to separating complexity classes.

share|improve this answer
As I wrote, I know for classes closed under composition(for linear TM you probably need many tape to make this true) I found the exact same problem then you when I tried to make the proof, (even if at first I was trying to make a descriptive complexity attemps, but that seems to be equivalent) My theory book is Arora Barak, which does not seems to discuss of bounded alternation after the poly-time classes, hence if you have got any references, both to state that this is open, and that under the condition that PTIME collapse it collapse, I'd like it please. Thanks for your help –  Arthur MILCHIOR Aug 9 '10 at 23:12
Here is one reference. See Theorem 3.2 in: oocities.com/stockmeyer@sbcglobal.net/pth.pdf. But this doesn't say that the problem is open for superpolynomial functions. I am not sure of a reference for that, but I do know that even if NEXP = EXP it is not known how to solve NEXP search problems in less than doubly-exponential time. This is essentially the same sort of problem you run into here. See Impagliazzo and Tardos 1989. –  Ryan Williams Aug 10 '10 at 0:39

Your Answer


