Collapsing of exptime and alternation bounded turing machine

Question

Hello

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

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.