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

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

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

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