10
$\begingroup$

This question was already asked on math overflow, 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($\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$ ?

$\endgroup$
  • 2
    $\begingroup$ Good luck finding a better answer :) $\endgroup$ – Ryan Williams Aug 24 '10 at 5:34
  • $\begingroup$ 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) $\endgroup$ – Arthur MILCHIOR Aug 24 '10 at 6:19
  • $\begingroup$ In this work on the exponential hierarchy, there is a small paragraph relating the hierarchy to defintions in terms of alternating Turing machines: ecommons.cornell.edu/handle/1813/6617 So you are not completely alone... $\endgroup$ – 5501 Apr 10 '11 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.