2
$\begingroup$

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.

  • 0
    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)$2011-05-11

1 Answers 1

2

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.

That of course is a rather lazy (never the less correct) way to prove it. If you have to provide an algorithm, you can either refer to the original paper ( http://eccc.hpi-web.de/eccc-reports/2004/TR04-094/ ) or you can look if you find a simpler one. Maybe the algorithm for USTCON on grid graphs is a bit easier.

  • 0
    The reduction isn't, but this result wasn't preseneted during lecture.2011-05-11