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$
4

0