2
$\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.

I suspect that PSPACE-complete$_{FPH}$ is just PSPACE. What more can be found about the two last defined classes ?

$\endgroup$

closed as off-topic by Gilles Jun 23 '15 at 18:58

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.