<p>The paper <a href="https://doi.org/10.1016/S0304-3975(00)00193-6" rel="noreferrer">Hyper-polynomial hierarchies and the polynomial jump</a> by Fenner, Homer, Pruim, and Schaefer seems to be relevant.</p>

CC BY-SA 4.0
2022-09-10T16:09:25.883Z
2022-09-10T16:09:25.883Z
user67422
<p>Sure, versions of the polynomial hierarchy &quot;with an unbounded number of alternations&quot; can be found in the literature.</p>
<p>One paper that stands out in my memory:
<a href="https://lance.fortnow.com/papers/files/npvsnl.pdf" rel="noreferrer">https://lance.fortnow.com/papers/files/npvsnl.pdf</a></p>

CC BY-SA 4.0
2022-09-17T03:24:01.247Z
2022-09-17T03:24:01.247Z
Ryan Williams
<p>I am interesting in languages of the following form:</p>
<p><span class="math-container">$x \in L \Leftrightarrow Q y_1 Q y_2 \ldots Q y_n P(x, y_1, \ldots y_n, x).$</span></p>
<p>Here every Q is <span class="math-container">$\forall$</span> or <span class="math-container">$\exists$</span>;</p>
<p><span class="math-container">$n$</span> is the length of <span class="math-container">$x$</span>,  the lengths of <span class="math-container">$y_i$</span> are bounded by poly(<span class="math-container">$n$</span>);</p>
<p><span class="math-container">$P$</span> is a polynomial-time computable function.</p>
<p>Denote by <span class="math-container">$m$</span> the number of alternations in this expression.</p>
<p>If <span class="math-container">$m$</span> is constant then <span class="math-container">$L \in \text{PH}$</span>; if <span class="math-container">$m=n-1$</span> then <span class="math-container">$L$</span> can be <span class="math-container">$\text{PSPACE}$</span>-complete.</p>
<p>Consider some intermediate <span class="math-container">$m$</span>, for example <span class="math-container">$m=O(\log n)$</span>.</p>
<p><strong>Question:</strong> Does anybody consider the class of corresponding languages
(for some <span class="math-container">$m = o(n))$</span>)?</p>
<p>Is there some established name for it?</p>

CC BY-SA 4.0
2022-09-26T04:44:57.067Z
Search for $\mathsf{AltTime}(\lg n, n^{O(1)})$.
Kaveh
CC BY-SA 4.0
2022-09-26T04:57:51.273Z
In some literature, it of also started as $\mathsf{ATimeAlt}(n^{O(1)}, \lg n)$

https://en.wikipedia.org/wiki/Alternating_Turing_machine
Kaveh
<cc.complexity-theory><complexity-classes>
Classes between PH and PSPACE
Alexey Milovanov
# Classes between PH and PSPACE

(Asked by: username_0 on 2022-09-10)

I am interesting in languages of the following form:

$x \in L \Leftrightarrow Q y\_1 Q y\_2 \ldots Q y\_n P(x, y\_1, \ldots y\_n, x).$

Here every Q is $\forall$ or $\exists$;

$n$ is the length of $x$, the lengths of $y\_i$ are bounded by poly($n$);

$P$ is a polynomial-time computable function.

Denote by $m$ the number of alternations in this expression.

If $m$ is constant then $L \in \text{PH}$; if $m=n-1$ then $L$ can be $\text{PSPACE}$-complete.

Consider some intermediate $m$, for example $m=O(\log n)$.

**Question:** Does anybody consider the class of corresponding languages
(for some $m = o(n))$)?

Is there some established name for it?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Search for $\mathsf{AltTime}(\lg n, n^{O(1)})$.  
> **username_1**: In some literature, it of also started as $\mathsf{ATimeAlt}(n^{O(1)}, \lg n)$  https://en.wikipedia.org/wiki/Alternating_Turing_machine  

---

## 2 answers

### Answer by username_2 on 2022-09-10. Score: 5

The paper [Hyper-polynomial hierarchies and the polynomial jump](https://doi.org/10.1016/S0304-3975(00)00193-6) by Fenner, Homer, Pruim, and Schaefer seems to be relevant.


---

### Answer by username_3 on 2022-09-17. Score: 5

Sure, versions of the polynomial hierarchy "with an unbounded number of alternations" can be found in the literature.

One paper that stands out in my memory:
<https://lance.fortnow.com/papers/files/npvsnl.pdf>


---

