3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Search for $\mathsf{AltTime}(\lg n, n^{O(1)})$. $\endgroup$
    – Kaveh
    Sep 26, 2022 at 4:44
  • $\begingroup$ In some literature, it of also started as $\mathsf{ATimeAlt}(n^{O(1)}, \lg n)$ en.wikipedia.org/wiki/Alternating_Turing_machine $\endgroup$
    – Kaveh
    Sep 26, 2022 at 4:57

2 Answers 2

5
$\begingroup$

The paper Hyper-polynomial hierarchies and the polynomial jump by Fenner, Homer, Pruim, and Schaefer seems to be relevant.

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.