<p>Let <span class="math-container">$\mathsf{AltTime}(g(n), f(n))$</span> denote the class of languages that are solvable by an alternating machine using <span class="math-container">$f(n)$</span> time and <span class="math-container">$g(n)$</span> alternations.</p>
<p>Is there anything known about the following relation:
<span class="math-container">$$\exists f(n)\ \exists g(n)\ \exists h(n)&lt;g(n):\mathsf{AltTime}(g(n),f(n))\subset \mathsf{AltTime}(h(n),2^{o(f(n))})/2^{o(n)}$$</span></p>
<p>I.e. how much smaller than <span class="math-container">$g(n)$</span> can <span class="math-container">$h(n)$</span> be (if at all) and at what (asymptotically) smallest <span class="math-container">$f(n)$</span> it holds.</p>
<p>Perhaps, something is also known about the relation with a smaller advice string or without an advice at all?</p>

CC BY-SA 4.0
2023-07-10T17:16:00.423Z
Do you allow $f(n) < n$?
Ryan Williams
CC BY-SA 4.0
2023-07-11T20:35:47.413Z
@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.
rus9384
<cc.complexity-theory><complexity-classes><time-complexity><advice-and-nonuniformity>
Reducing the amount of alternations without exponentially increasing the runtime?
rus9384
# Reducing the amount of alternations without exponentially increasing the runtime?

(Asked by: username_0 on 2023-07-07)

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)

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?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, advice-and-nonuniformity
> **Comments:**
> **username_1**: Do you allow $f(n) < n$?  
> **username_0**: @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.  

---

## 0 answers

