Why not polynomial-space reductions for $PSPACE$-hardness?

Question

A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$.

Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$.

Why does we use time reductions instead of space reductions in this situation?

Answer 1

It's never interesting to use reductions that are as powerful as the complexity class you're talking about. With the exception of $\emptyset$ and $\Sigma^*$, every problem in $\mathbf{PSPACE}$ is $\mathbf{PSPACE}$-complete under poly-space reductions.

To see this, let $X\in \mathbf{PSPACE}\setminus\{\emptyset,\Sigma^*\}$, and choose any fixed pair of strings strings $y\in X$ and $n\notin X$. Now, for any language $L\in\mathbf{PSPACE}$, we can reduce $L$ to $X$ using the function $$f(w)=\begin{cases}\ y&\text{if }w\in L\\ \ n&\text{if }w\notin L.\end{cases}$$ Since $L\in\mathbf{PSPACE}$, we can compute $f$ in polynomial space.

This argument applies for any reasonable complexity class and it's the reason why, for example, we don't talk about problems being $\mathbf{P}$-complete under poly-time reductions: instead, we use something like log-space reductions, there.

In general, hardness or completeness results are "more impressive" using weaker reductions, since the reduction is able to do less of the work. In the case of $\mathbf{PSPACE}$-completeness under poly-space reductions, the reduction is actually doing all the work.