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

Posted on Categories proxies

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

Posted on Categories proxies

## How to verify Hamilton-Path in log-space?

Given an undirected graph $$G$$ and an undirected path $$p$$, Is it possible to verify $$p$$ is a Hamilton path in graph $$G$$ using logarithmic space? How is it possible to verify the path goes through all vertices without somehow save which one had been already checked?

Posted on Categories proxies

## Log-space reduction – How to calculate overall space needed?

Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed by an algorithm which solves A using this reduction?

Posted on Categories proxies

## 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.

Posted on Categories proxies

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

Posted on Categories proxies