Let $\mathsf{AltTime}(g(n), f(n))$ denote the class of languages that are solvable by an alternating machine using $f(n)$ time and $g(n)$ alternations.

Is there anything known about the following relation: $$\exists f(n)\ \exists g(n)\ \exists h(n)<g(n):\mathsf{AltTime}(g(n),f(n))\subset \mathsf{AltTime}(h(n),2^{o(f(n))})/2^{o(n)}$$

I.e. how much smaller than $g(n)$ can $h(n)$ be (if at all) and at what (asymptotically) smallest $f(n)$ it holds.

Perhaps, something is also known about the relation with a smaller advice string or without an advice at all?

  • $\begingroup$ Do you allow $f(n) < n$? $\endgroup$ Jul 10, 2023 at 17:16
  • $\begingroup$ @RyanWilliams The motivation for this is that if for some class $C=DTIME(f(n))$ the hierarchy $C^{PH}$ collapses, then this relation is true for $h(n)=g(n)-k$ for any fixed $k$, but this relation is a weaker statement. $\endgroup$
    – rus9384
    Jul 11, 2023 at 20:35


Your Answer

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