<p>We generally define $PH = \cup_i\Sigma_i^p$ (or various equivalent forms.)  In the same notation we can also define $PSPACE = \cup_c\Sigma_{n^c}^p$--that is, like the polynomial hierarchy, but with a polynomial number of alternations between $\exists$ and $\forall$ quantifiers.</p>

<p>I have never seen, after looking around quite a bit, anyone define a class with more than a constant number of alternations but less than polynomial, say $\Sigma_{\log n}^p$ or even $\Sigma_{(\log n)^c}^i$.  Given how many tiny differences in computational power get exhaustively studied, this confuses me. Is this a named or studied class? If not, is there a good reason why (does it reduce trivially to something else?)</p>

<p>While this may seem arbitrary, I think it's a natural class to consider, in particular if we look at circuit formulations: $PH$ is precisely the class of (uniform) constant-depth, exponential sized, unlimited-fanin circuits, and $PSPACE$ the class of the same circuits of polynomial depth; it seems very natural to consider logarithmic (or polylogarithmic) depth circuits.</p>

CC BY-SA 3.0
2017-09-01T06:42:11.393Z
AltTime(lg n, poly(n))
Kaveh
CC BY-SA 3.0
2017-09-05T16:27:44.533Z
This post may be somewhat relevant: https://cstheory.stackexchange.com/questions/37614/quantified-boolean-formulas-with-logarithmic-alternations
Michael Wehar
CC BY-SA 3.0
2017-09-05T17:02:11.333Z
When it comes to alternating Turing machines.  To my knowledge, people have considered trade-offs between time, space, number of alternations, and witness size per alternation (i.e. number of bits per quantifier).  Although, I don't know of many published results on the subject.  If you're interested in this subject, please let me know as I'm fond of this area.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-08T21:45:40.963Z
In fact it may be useful if such a class is contained in $\mathsf{CH}$.
rus9384
<cc.complexity-theory><complexity-classes>
Logarithmic levels of the polynomial hierarchy (below PSPACE)
ahh
# Logarithmic levels of the polynomial hierarchy (below PSPACE)

(Asked by: username_0 on 2017-09-01)

We generally define $PH = \cup\_i\Sigma\_i^p$ (or various equivalent forms.) In the same notation we can also define $PSPACE = \cup\_c\Sigma\_{n^c}^p$--that is, like the polynomial hierarchy, but with a polynomial number of alternations between $\exists$ and $\forall$ quantifiers.

I have never seen, after looking around quite a bit, anyone define a class with more than a constant number of alternations but less than polynomial, say $\Sigma\_{\log n}^p$ or even $\Sigma\_{(\log n)^c}^i$. Given how many tiny differences in computational power get exhaustively studied, this confuses me. Is this a named or studied class? If not, is there a good reason why (does it reduce trivially to something else?)

While this may seem arbitrary, I think it's a natural class to consider, in particular if we look at circuit formulations: $PH$ is precisely the class of (uniform) constant-depth, exponential sized, unlimited-fanin circuits, and $PSPACE$ the class of the same circuits of polynomial depth; it seems very natural to consider logarithmic (or polylogarithmic) depth circuits.

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

> **Comments:**
> **username_1**: AltTime(lg n, poly(n))  
> **username_2**: This post may be somewhat relevant: https://cstheory.stackexchange.com/questions/37614/quantified-boolean-formulas-with-logarithmic-alternations  
> **username_2**: When it comes to alternating Turing machines.  To my knowledge, people have considered trade-offs between time, space, number of alternations, and witness size per alternation (i.e. number of bits per quantifier).  Although, I don't know of many published results on the subject.  If you're interested in this subject, please let me know as I'm fond of this area.  :)  
> **username_3**: In fact it may be useful if such a class is contained in $\mathsf{CH}$.  

---

## 0 answers

