<p>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]. <br>
It has been shown that 
  PH
  &#x2286;
  MP
&#x2286;
 PSPACE

.</p>

CC BY-SA 3.0
2012-02-18T21:55:39.837Z
2012-02-18T21:55:39.837Z
Tayfun Pay
<p>The <a href="http://en.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="noreferrer">existential theory of the reals</a> 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.</p>

CC BY-SA 3.0
2012-02-20T14:44:13.847Z
What do you mean by a complete problem? The existential theory of the reals is a single problem, not a class.
Emil Jeřábek
CC BY-SA 3.0
2012-02-20T14:50:00.887Z
@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.
Peter Shor 
CC BY-SA 3.0
2012-02-20T15:41:08.470Z
I see, this makes sense.
Emil Jeřábek
CC BY-SA 3.0
2011-05-08T22:51:28.233Z
2012-02-20T15:43:24.787Z
2012-02-20T15:43:24.787Z
Peter Shor 
<p>Any <a href="http://en.wikipedia.org/wiki/PP_%28complexity%29">PP</a>-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 <a href="http://en.wikipedia.org/wiki/Toda%27s_theorem">Toda's theorem</a> that PH is contained in P$^\text{PP}$. I believe the same also applies for <a href="http://en.wikipedia.org/wiki/Sharp-P">#P</a>-complete problems.</p>

CC BY-SA 3.0
2011-05-08T22:47:59.030Z
2011-05-09T22:14:39.797Z
2011-05-09T22:14:39.797Z
Dai Le
<p>Copying my comment:</p>

<p>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. </p>

CC BY-SA 3.0
2011-05-09T01:32:43.193Z
2011-05-09T01:32:43.193Z
Robin Kothari
<p>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. </p>

CC BY-SA 3.0
2012-02-20T18:13:32.870Z
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.
Tayfun Pay
CC BY-SA 3.0
2012-02-20T15:07:43.517Z
2012-02-20T15:07:43.517Z
Bin Fu
<p>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? </p>

CC BY-SA 3.0
2011-05-08T20:51:57.427Z
Any PSPACE-complete problem? Maybe you ask the wrong question.
5501
CC BY-SA 3.0
2011-05-08T20:56:14.623Z
Are you asking whether PH=PSPACE?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-05-08T21:13:15.593Z
I think the OP is merely asking whether there are any plausible candidates for separating PH and PSPACE
Suresh Venkat
CC BY-SA 3.0
2011-05-08T21:24:41.603Z
I believe there is a theorem which states that if PSPACE=PH then PH collapses.. I think I read it in Papadimitrou's book...
Tayfun Pay
CC BY-SA 3.0
2011-05-08T21:24:55.677Z
@Suresh, that is exactly what I am asking!
Tayfun Pay
CC BY-SA 3.0
2011-05-08T21:56:20.547Z
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.
Robin Kothari
CC BY-SA 3.0
2011-05-08T22:01:00.783Z
Also, the existential theory of the reals is known to be in PSPACE but not PH.
Peter Shor 
CC BY-SA 3.0
2011-05-08T22:34:46.643Z
@Robin, @Peter, both of these are answers, not comments :)
Suresh Venkat
CC BY-SA 3.0
2012-08-02T14:16:04.753Z
To the person whom that change their vote from upvote to downvote 1.5 years later.... Grow up!
Tayfun Pay
<cc.complexity-theory><complexity-classes>
A problem that is in PSPACE but not known to be in PH?
Tayfun Pay
# A problem that is in PSPACE but not known to be in PH?

(Asked by: username_0 on 2011-05-08)

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?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Any PSPACE-complete problem? Maybe you ask the wrong question.  
> **username_2**: Are you asking whether PH=PSPACE?  
> **username_3**: I think the OP is merely asking whether there are any plausible candidates for separating PH and PSPACE  
> **username_0**: I believe there is a theorem which states that if PSPACE=PH then PH collapses.. I think I read it in Papadimitrou's book...  
> **username_0**: @Suresh, that is exactly what I am asking!  
> **username_4**: 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.  
> **username_5**: Also, the existential theory of the reals is known to be in PSPACE but not PH.  
> **username_3**: @Robin, @Peter, both of these are answers, not comments :)  
> **username_0**: To the person whom that change their vote from upvote to downvote 1.5 years later.... Grow up!  

---

## 5 answers

### Answer by username_0 on 2012-02-18. Score: 1 | Accepted answer

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
.


---

### Answer by username_5 on 2011-05-08. Score: 23

The [existential theory of the reals](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_6**: What do you mean by a complete problem? The existential theory of the reals is a single problem, not a class.  
> **username_5**: @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.  
> **username_6**: I see, this makes sense.  

---

### Answer by username_7 on 2011-05-08. Score: 19

Any [PP](http://en.wikipedia.org/wiki/PP_%28complexity%29)-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](http://en.wikipedia.org/wiki/Toda%27s_theorem) that PH is contained in P$^\text{PP}$. I believe the same also applies for [#P](http://en.wikipedia.org/wiki/Sharp-P)-complete problems.


---

### Answer by username_4 on 2011-05-09. Score: 18

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.


---

### Answer by username_8 on 2012-02-20. Score: 1

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.

> **Comments:**
> **username_0**: 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.  

---

