3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I see. This brings up two new questions for me then: 1) It might be reasonable to use something like log-space reductions then? 2) The reason we don't use poly-space reductions for $NPSPACE$ is because of Savitch's theorem (along with the argument used in your answer)? $\endgroup$ – theQman Sep 4 '18 at 14:50
  • $\begingroup$ @theQman Yes, logspace reductions would make sense for PSPACE; they're often used for NP, too. In practice, we tend not to use reductions more powerful than poly-time for any complexity class: the extra power doesn't seem to buy you very much and it's easier to compare things if we're more consistent about what kind of reductions we use. You're right about NPSPACE and Savitch. $\endgroup$ – David Richerby Sep 4 '18 at 15:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.