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?
$\begingroup$
$\endgroup$
9
-
4$\begingroup$ Any PSPACE-complete problem? Maybe you ask the wrong question. $\endgroup$– 5501May 8, 2011 at 20:51
-
1$\begingroup$ Are you asking whether PH=PSPACE? $\endgroup$– Mohammad Al-TurkistanyMay 8, 2011 at 20:56
-
11$\begingroup$ 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. $\endgroup$– Robin KothariMay 8, 2011 at 21:56
-
7$\begingroup$ Also, the existential theory of the reals is known to be in PSPACE but not PH. $\endgroup$– Peter ShorMay 8, 2011 at 22:01
-
4$\begingroup$ @Robin, @Peter, both of these are answers, not comments :) $\endgroup$– Suresh VenkatMay 8, 2011 at 22:34
|
Show 4 more comments
5 Answers
$\begingroup$
$\endgroup$
3
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.
answered May 8, 2011 at 22:51
-
$\begingroup$ What do you mean by a complete problem? The existential theory of the reals is a single problem, not a class. $\endgroup$ Feb 20, 2012 at 14:44
-
1$\begingroup$ @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. $\endgroup$ Feb 20, 2012 at 14:50
-
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered May 9, 2011 at 1:32
$\begingroup$
$\endgroup$
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
.
answered Feb 18, 2012 at 21:55
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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. $\endgroup$ Feb 20, 2012 at 18:13