5
$\begingroup$

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. This class is known as PSPACE-complete.

Similarly, we can define :

PSPACE-complete$_{FPSPACE}$ problems, the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial space reduction. This class is still PSPACE, minus trivial problems $\Sigma^*$ and $\emptyset$.

PSPACE-complete$_{FNP}$ problems, the PSPACE problems such that every other PSPACE problem can be transformed to it with a FNP reduction (the function problem extension of the decision problem class NP).

PSPACE-complete$_{FPH}$ problems, the PSPACE problems such that every other PSPACE problem can be transformed to it with a FPH reduction (the function problem extension of the decision problem class PH).

It seems to me that all these classes are well defined and that we have :

PSPACE-complete $\subset$ PSPACE-complete$_{FNP}$ $\subset$ PSPACE-complete$_{FPH}$ $\subset$ PSPACE

Additionally, if PSPACE-complete$_{FPH}$ $\neq$ PSPACE-complete then P $\neq$ NP.

Naturally, PSPACE-complete$_{FNP}$ $\neq$ PSPACE-complete works also but it's more difficult to prove.

What more can be found about the two last defined classes ?

(Initially asked on cs.stackexchange.com)

$\endgroup$
  • 1
    $\begingroup$ Not much, probably. Anyway, what do you mean by “trivial problems”? For instance, PP-complete problems are likely not PSPACE-complete under FPH-reductions, but nontrivial in the sense of not being in PH. See also cstheory.stackexchange.com/q/799 . $\endgroup$ – Emil Jeřábek supports Monica Jun 18 '15 at 14:05
  • 2
    $\begingroup$ Crosspost on cs.SE. $\endgroup$ – Raphael Jun 18 '15 at 14:33
  • 1
    $\begingroup$ Then it makes even less sense. Clearly, there are nontrivial problems in PSPACE that are not complete under FPH-reductions unless PSPACE=PH (whence PH collapses). $\endgroup$ – Emil Jeřábek supports Monica Jun 18 '15 at 14:43
  • $\begingroup$ PH is closed under FPH reductions. So, no nontrivial problem in PH, such as $\{0\}$, is PSPACE-complete under FPH-reductions unless PSPACE=PH. $\endgroup$ – Emil Jeřábek supports Monica Jun 18 '15 at 16:15
  • 1
    $\begingroup$ I think this is a good question. :) $\endgroup$ – Michael Wehar Jun 20 '15 at 23:53

Your Answer

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

Browse other questions tagged or ask your own question.