<p><em>PSPACE-complete$_{FP}$</em> problems are the <em>PSPACE</em> problems such that every other <em>PSPACE</em> problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fp" rel="nofollow noreferrer"><em>FP</em></a>. This class is known as <em>PSPACE-complete</em>.</p>

<p>Similarly, we can define :</p>

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

<p><em>PSPACE-complete$_{FNP}$</em> problems, the  <em>PSPACE</em> problems such that every other <em>PSPACE</em> problem can be transformed to it with a <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fnp" rel="nofollow noreferrer"><em>FNP</em></a> reduction (the function problem extension of the decision problem class <em>NP</em>).</p>

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

<p>It seems to me that all these classes are well defined and that we have :</p>

<p><em>PSPACE-complete</em> $\subset$ <em>PSPACE-complete$_{FNP}$</em> $\subset$ <em>PSPACE-complete$_{FPH}$</em> $\subset$ <em>PSPACE</em></p>

<p>Additionally, if <em>PSPACE-complete$_{FPH}$</em> $\neq$ <em>PSPACE-complete</em> then <em>P</em> $\neq$ <em>NP</em>.</p>

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

<p>What more can be found about the two last defined classes ?</p>

<p>(Initially asked on <a href="https://cs.stackexchange.com/questions/40946/pspace-completeness-with-different-kinds-of-reductions">cs.stackexchange.com</a>)</p>

CC BY-SA 3.0
2015-06-18T14:33:48.230Z
[Crosspost on cs.SE](http://cs.stackexchange.com/questions/40946/pspace-completeness-with-different-kinds-of-reductions).
Raphael
CC BY-SA 3.0
2015-06-20T12:43:26.947Z
Previous outdated comments deleted. A quite similar question : http://cstheory.stackexchange.com/questions/25316/nexptime-completeness-with-more-time-for-reductions
François
CC BY-SA 3.0
2015-06-20T23:53:32.150Z
I think this is a good question.  :)
Michael Wehar
<cc.complexity-theory><complexity-classes><reductions><space-complexity>
PSPACE completeness, with different kinds of reductions
François
# PSPACE completeness, with different kinds of reductions

(Asked by: username_0 on 2015-06-18)

*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*](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#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*](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#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](https://cs.stackexchange.com/questions/40946/pspace-completeness-with-different-kinds-of-reductions))

**Tags:** cc.complexity-theory, complexity-classes, reductions, space-complexity

> **Comments:**
> **username_1**: [Crosspost on cs.SE](http://cs.stackexchange.com/questions/40946/pspace-completeness-with-different-kinds-of-reductions).  
> **username_0**: Previous outdated comments deleted. A quite similar question : http://cstheory.stackexchange.com/questions/25316/nexptime-completeness-with-more-time-for-reductions  
> **username_2**: I think this is a good question.  :)  

---

## 0 answers

