# Special case connectivity in LOGSPACE

Consider a grid, $N x N$ in size, with cells colored white or black. It can be encoded naturally by a word from $\{0,1\}^{n^2}$. Show that a deterministic Turing machine with logarithimic memory can decide if there exists a monochromatic path from the top row to the borrom row.

Allowed moves: up, down, left, right. No diagonal moves.

This isn't homework, but a question from a quiz I've taken today.

Paths can be very long, even $O(n^2)$ in size, so performing a DFS/BFS simulation is not possible. Methods like "right hand rule" for solving mazes seem not applicable.

-
What if you only keep track of the cells in the path that turn a different direction from the previous cell's direction? I'm thinking that would still need linear space... but it's better than $O(n^2)$ – Nicolas Villanueva May 11 '11 at 19:30

You can prove this by simply reducing your problem to general st-connectivity for undirected graphs. Every cell is a node, connected to its neighbours iff it has the same color. Additionally you add 2 nodes. one that connects to every cell in the top row, one that connects to every cell in the bottom row. That problem then is solvable in $L$, as Omer Reingold proved in 2004.