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 }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 ?

Log-Space Reduction $USTCON\le_L CO-2Col$

I want to show that $ USTCON\le_L CO-2Col$ (Log-Space reduction)

$ USTCON$ The $ s-t$ connectivity problem for undirected graphs is called $ USTCON$ .

Input: An undirected graph $ G=(V,E)$ , $ s,t \in V$ . Output: 1 iff $ s$ is connected to $ t$ in $ G$ .

$ CO-2Col$ A graph is $ 2$ -colorable if there is a way to color the vertices of $ G$ with $ 2$ colors, such that for every edge the two vertices on the edge are colored differently. $ CO-2Col$ is the following problem:

Input: An undirected graph $ G$ . Output: 1 iff $ G$ is NOT $ 2$ -colorable.

I know this can be solved by simply using the $ USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

Constructing a DFA $M$ such that $L(M) = L(A) \triangle L(B)$ with a kind of log-space TM

Suppose that $ A$ and $ B$ are DFAs. We know that there is some DFA $ M$ such that $ L(M) = L(A) \triangle L(B)$ . Also, we can construct this $ M$ by some Turing machine $ N$ . But can we ensure that $ N$ has the following form?

  • $ N$ consists of (i) a read-only input tape, (ii) a work tape that is log-space with respect to $ |\langle A, B\rangle|$ , and (iii) a one-way, write-only, polynomial-time output tape.

This really comes down to showing that this kind of TM can construct DFAs for $ L(A) \cup L(B)$ and $ L(A) \cap L(B)$ . But it’s not clear to me how this would work.

Any help is appreciated.

Reachibility between first and last layer in grid graph in logspace

I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $ 0s$ and $ 1s$ , the undirected edge exists between two $ 0s$ or $ 1s$ – one the left, right, up, down. Path can contains only $ 0s$ or only $ 1s$ .

For example in following graph there exists such path:

0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 

For following there is no such path

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1  

How to prove it ?