<p>This question was already asked on <a href="https://mathoverflow.net/questions/35008/collapsing-of-exptime-and-alternation-bounded-turing-machine">math overflow</a>, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)</p>

<p>Let C be a set of function (let say time-computable increasing function to avoid pathological cases).
Let's call $\Sigma_j\rm{TIME}(C)$ the class of languages decided by a Turing Machine beginning in existential state, alternating at most $j-1$ times and whose time is bounded by a function $f\in C$.</p>

<p>Let suppose that $\Sigma_j\rm{TIME}(C)=\Sigma_{j+1}\rm{TIME}(C)$ then, can we prove that $\forall k&gt;j \Sigma_j\rm{TIME}(C)=\Sigma_k\rm{TIME}(C)$ ? Or at least, what are the condition over $C$ ?</p>

<p>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 bounded tower of 2.)</p>

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

<p>There is at least one related result I can state, which is that if $\Sigma_j\rm{TIME}(\exp_2^c(n^{O(1)}))=\Sigma_k\rm{TIME}(\exp_2^c(n^{O(1)}))$ then $\Sigma_j\rm{TIME}(\exp_2^d(n^{O(1)}))=\Sigma_k\rm{TIME}(\exp_2^d(n^{O(1)}))$ for $d&gt;c$ where $\exp_2^j(n)$ use the notation for <a href="http://en.wikipedia.org/wiki/Tetration" rel="nofollow noreferrer">tetration</a>($\exp_2^d(n^{O(1)})=\{2^{2^{\dots^{2^{n^{O(1)}}}}}\}$ with $d$ "2"s). </p>

<p>In fact I have a more general result, but this give a good idea. If anything like this is already known, I would like to know the references.</p>

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

<p>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 existential quantification. </p>

<p>If there exists $k&gt;2$ such that HO$^{r,2}_j$=HO$^{r,f}_k$ then can we prove that  $\forall l&gt;j$  HO$^{r,2}_j$=HO$^{r,2}_l$ ?</p>

CC BY-SA 3.0
2011-04-10T18:52:43.333Z
In this work on the exponential hierarchy, there is a small paragraph relating the hierarchy to defintions in terms of alternating Turing machines: http://ecommons.cornell.edu/handle/1813/6617 So you are not completely alone...
5501
CC BY-SA 2.5
2010-08-24T05:34:36.170Z
Good luck finding a better answer :)
Ryan Williams
CC BY-SA 2.5
2010-08-24T06:19:13.767Z
Thank you. I guess at least it's worth asking; because I am surprise I can not even find a reference stating that this question is open. And it seems natural enough for me, so I'm pretty sure I was not the first one wondering about this kind of classes. (Even if there may not have been a lot of people looking at descriptive complexity with high order relations)
Arthur MILCHIOR
<cc.complexity-theory><conditional-results><descriptive-complexity><alternating-hierarchy>
Collapsing of exptime and alternation bounded turing machine
Arthur MILCHIOR
# Collapsing of exptime and alternation bounded turing machine

(Asked by: username_0 on 2010-08-24)

This question was already asked on [math overflow](https://mathoverflow.net/questions/35008/collapsing-of-exptime-and-alternation-bounded-turing-machine), but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)

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

Let suppose that $\Sigma\_j\rm{TIME}(C)=\Sigma\_{j+1}\rm{TIME}(C)$ then, can we prove that $\forall k>j \Sigma\_j\rm{TIME}(C)=\Sigma\_k\rm{TIME}(C)$ ? 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 bounded 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 adviser could.

There is at least one related result I can state, which is that if $\Sigma\_j\rm{TIME}(\exp\_2^c(n^{O(1)}))=\Sigma\_k\rm{TIME}(\exp\_2^c(n^{O(1)}))$ then $\Sigma\_j\rm{TIME}(\exp\_2^d(n^{O(1)}))=\Sigma\_k\rm{TIME}(\exp\_2^d(n^{O(1)}))$ for $d>c$ where $\exp\_2^j(n)$ use the notation for [tetration](http://en.wikipedia.org/wiki/Tetration)($\exp\_2^d(n^{O(1)})=\{2^{2^{\dots^{2^{n^{O(1)}}}}}\}$ with $d$ "2"s).

In fact I have a more general result, but this give a good idea. If anything like this is already known, I would like to know the references.

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 existential quantification.

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

**Tags:** cc.complexity-theory, conditional-results, descriptive-complexity, alternating-hierarchy
> **Comments:**
> **username_2**: Good luck finding a better answer :)  
> **username_0**: Thank you. I guess at least it's worth asking; because I am surprise I can not even find a reference stating that this question is open. And it seems natural enough for me, so I'm pretty sure I was not the first one wondering about this kind of classes. (Even if there may not have been a lot of people looking at descriptive complexity with high order relations)  
> **username_1**: In this work on the exponential hierarchy, there is a small paragraph relating the hierarchy to defintions in terms of alternating Turing machines: http://ecommons.cornell.edu/handle/1813/6617 So you are not completely alone...  

---

## 0 answers

