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