8
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Any PSPACE-complete problem? Maybe you ask the wrong question. $\endgroup$ – 5501 May 8 '11 at 20:51
  • 1
    $\begingroup$ Are you asking whether PH=PSPACE? $\endgroup$ – Mohammad Al-Turkistany May 8 '11 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 Kothari May 8 '11 at 21:56
  • 7
    $\begingroup$ Also, the existential theory of the reals is known to be in PSPACE but not PH. $\endgroup$ – Peter Shor May 8 '11 at 22:01
  • 4
    $\begingroup$ @Robin, @Peter, both of these are answers, not comments :) $\endgroup$ – Suresh Venkat May 8 '11 at 22:34
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by a complete problem? The existential theory of the reals is a single problem, not a class. $\endgroup$ – Emil Jeřábek Feb 20 '12 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$ – Peter Shor Feb 20 '12 at 14:50
  • $\begingroup$ I see, this makes sense. $\endgroup$ – Emil Jeřábek Feb 20 '12 at 15:41
19
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 .

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – Tayfun Pay Feb 20 '12 at 18:13

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.