That is, is there a problem that all problems in the polynomial hierarchy can be reduced to in polynomial time, but which some PSPACE problem cannot be reduced to in polynomial time? Clearly if the polynomial hierarchy collapses, then there is such a problem if and only if $PH\neq PSPACE$. Is it known whether there is such a problem, or are there reasons for suspecting one way or the other, assuming the polynomial hierarchy does not collapse?

  • 2
    $\begingroup$ Does $P^{\#P}$ contain complete problems? $\endgroup$ – Alexey Milovanov Jan 28 '17 at 21:26
  • 1
    $\begingroup$ @Alexey : Yes, $P^{\#P}$ is a syntactic class; you can easily enumerate all polynomially clocked machines with access to a subroutine that computes permanents (the clock charges only unit time for each subroutine call). $\endgroup$ – Timothy Chow Jan 29 '17 at 2:50

Alexander Shen suggests the following language that is PH-hard,

but does not seem to be PSPACE-hard:

STRANGE TQBF $f \in L \Leftrightarrow \forall y_1 \exists y_2 \exists y_3 \forall y_4 \forall y_5 \forall y_6 \forall y_7 \ldots f(y_1, y_2, \ldots, y_n) =1$.

(So there are $O(\log n)$ changes of quantifiers, $f$ is a boolean formula.)


This is almost a duplicate of this question. If PH does not collapse then PH≠PSPACE. It is a theorem of Schöning that if PH≠PSPACE then there exists a language L in PSPACE∖PH that is not PSPACE-complete.

However, I don't see how to use Schöning's argument to show that L is actually PH-hard (as opposed to merely not being in PH). I'm not sure if it is known whether the existence of such an L follows from the assumption that PH does not collapse.


Your Answer

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

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