patternMinor
Why not polynomial-space reductions for $PSPACE$-hardness?
Viewed 0 times
whyspacepolynomialhardnesspspaceforreductionsnot
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#96947, answer score: 5
Revisions (0)
No revisions yet.