# Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction.

According to these posts :

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

PSpace-completeness under PSpace reductions

Every PSPACE language would be PSPACE-Complete if we defined completeness using a Poly-SPACE reduction (instead of a poly-TIME reduction).

My question is, why does Log-space reduction doesn't imply completeness for every $$L \in NL$$, for the same reasoning?

Take any A,B $$\in$$ NL , and fixed $$y,n$$ s.t $$y\in A$$ and $$n\notin A$$.

We can define the following log-space reduction $$f$$ : $$f(x)=\begin{cases}\ y&\text{if }x\in A\\ \ n&\text{if }x\notin A.\end{cases}$$

Just solve A in log-space and let our output be the fixed instance according to the right case.

How come log-space reductions are NOT useless for NL completeness while Pspace reductions are useless for PSPACE completeness? What am I missing ?

• Your reduction runs in nondeterministic logspace, but not necessarily in deterministic logspace. Sep 30 '19 at 14:05
• @YuvalFilmus So ; $f(x)$ needs to be computed using a determenistic TM , and thus my reduction runs in nondeterministic logspace- since solving provlem A might require using a nondeterministic machine (since $A \in NL$) While since $PSPACE = NPSPACE$ every problem in NPSPACE is also solveable in poly-space using a determenistic TM , thus the function $f(x)$ runs in determenistic time , and the reduction works as required ? Sep 30 '19 at 14:15
• It is conjectured that L and NL are different. Savitch’s theorem, used to show that PSPACE=NPSPACE, only implies that NL can be simulated in space $O(\log^2n)$. Sep 30 '19 at 14:17
• @YuvalFilmus Got it ! Thank you very much ! Sep 30 '19 at 14:21

Your reduction $$f$$ works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete.
What might be confusing you is that PSPACE=NPSPACE, which is proved using Savitch's theorem. In the context of logarithmic space, the theorem only shows that problems in NL can be decided in space $$O(\log^2 n)$$.