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 ?
-
$\begingroup$ Your reduction runs in nondeterministic logspace, but not necessarily in deterministic logspace. $\endgroup$Yuval Filmus– Yuval Filmus2019年09月30日 14:05:23 +00:00Commented Sep 30, 2019 at 14:05
-
$\begingroup$ @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 ? $\endgroup$Tomer.Ov– Tomer.Ov2019年09月30日 14:15:11 +00:00Commented Sep 30, 2019 at 14:15
-
$\begingroup$ 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)$. $\endgroup$Yuval Filmus– Yuval Filmus2019年09月30日 14:17:04 +00:00Commented Sep 30, 2019 at 14:17
-
$\begingroup$ @YuvalFilmus Got it ! Thank you very much ! $\endgroup$Tomer.Ov– Tomer.Ov2019年09月30日 14:21:12 +00:00Commented Sep 30, 2019 at 14:21
1 Answer 1
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)$.
Explore related questions
See similar questions with these tags.