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.

  • 2
    $\begingroup$ AltTime(lg n, poly(n)) $\endgroup$ – Kaveh Sep 1 '17 at 6:42
  • $\begingroup$ This post may be somewhat relevant: cstheory.stackexchange.com/questions/37614/… $\endgroup$ – Michael Wehar Sep 5 '17 at 16:27
  • 1
    $\begingroup$ 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. :) $\endgroup$ – Michael Wehar Sep 5 '17 at 17:02
  • $\begingroup$ In fact it may be useful if such a class is contained in $\mathsf{CH}$. $\endgroup$ – rus9384 Sep 8 '17 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.