1
$\begingroup$

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 }w\in A\\ \ n&\text{if }w\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 ?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Your reduction runs in nondeterministic logspace, but not necessarily in deterministic logspace. $\endgroup$ – Yuval Filmus Sep 30 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 Sep 30 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 Sep 30 at 14:17
  • $\begingroup$ @YuvalFilmus Got it ! Thank you very much ! $\endgroup$ – Tomer.Ov Sep 30 at 14:21
1
$\begingroup$

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)$.

|cite|improve this answer
$\endgroup$

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.