9

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.

ahh
  • 223
  • 1
  • 2
  • 2
    AltTime(lg n, poly(n)) – Kaveh Sep 01 '17 at 06:42
  • This post may be somewhat relevant: https://cstheory.stackexchange.com/questions/37614/quantified-boolean-formulas-with-logarithmic-alternations – Michael Wehar Sep 05 '17 at 16:27
  • 1
    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 Sep 05 '17 at 17:02
  • In fact it may be useful if such a class is contained in $\mathsf{CH}$. – rus9384 Sep 08 '17 at 21:45

0 Answers0