# A problem that is in PSPACE but not known to be in PH?

As we know Graph Isomorphism is in NP but it is not known to be NP-Complete or P-Complete. I was wondering if there are any problems that are known to be in PSPACE but not known to be PSPACE-Complete and not lie in PH?

• Any PSPACE-complete problem? Maybe you ask the wrong question.
– 5501
Commented May 8, 2011 at 20:51
• Are you asking whether PH=PSPACE? Commented May 8, 2011 at 20:56
• If you meant to ask for a problem analogous to GI, then perhaps you're asking for a problem that's not in PH and not PSPACE-complete. Problems complete for any class not known to be contained in PH, but contained in PSPACE, will work as an example. So take any problem complete for BQP, QMA, PP, etc. Commented May 8, 2011 at 21:56
• Also, the existential theory of the reals is known to be in PSPACE but not PH. Commented May 8, 2011 at 22:01
• @Robin, @Peter, both of these are answers, not comments :) Commented May 8, 2011 at 22:34

The existential theory of the reals is known to be contained in PSPACE, but it is not known whether it is contained in PH. So take the existential theory of the reals, or any of the many equivalent problems.

• What do you mean by a complete problem? The existential theory of the reals is a single problem, not a class. Commented Feb 20, 2012 at 14:44
• @Emil: fixed now. There are enough equivalent problems that I think of it also as a complexity class, but I'm in the minority here. Commented Feb 20, 2012 at 14:50
• I see, this makes sense. Commented Feb 20, 2012 at 15:41

Any PP-complete problem is trivially in PSPACE, but of course not known to be PSPACE-complete. We also don't know whether or not PP is contained in PH either, though it follows from Toda's theorem that PH is contained in P$^\text{PP}$. I believe the same also applies for #P-complete problems.

Copying my comment:

If you meant to ask for a problem analogous to GI, then perhaps you're asking for a problem that's not in PH and not PSPACE-complete. Problems complete for any class not known to be contained in PH, but contained in PSPACE, will work as an example. So take any problem complete for BQP, QMA, PP, etc.

Any problem that is MP-Complete, The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1. [Definition is from Complexity Zoo].
It has been shown that PH ⊆ MP ⊆ PSPACE .

ParitySat problem is to check if a SAT problem has an odd number of satisfiable assignments. PH is reducible to ParitySAT via randomized reductions by Toda’s work. This is a decision problem that is clearly strictly between PH and PSACE unless PH collapses.

• Yes there are two corollaries of Toda's theorem which states that ParityP nor PP are in PH unless PH collapses to a finite level. Commented Feb 20, 2012 at 18:13