Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
there should be an easier way, considering that this problem was on a quiz... –  blu May 11 '11 at 19:53
    
That depends on the class in which you took the quiz and the precise question (whether you had to specify the algorithm or not). The reduction to USTCON isn't too hard for an introduction lecture in TCS, in my opinion. –  Mike B. May 11 '11 at 20:50
    
The reduction isn't, but this result wasn't preseneted during lecture. –  blu May 11 '11 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.