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

• en.wikipedia.org/wiki/SL_(complexity) – D.W. May 3 '17 at 1:10
• Being honestly I don't know where are you going. At the bottom of your link: It is also now known that a problem is in L if and only if it is log-space reducible to USTCON. Oh, yes. I can reduce my problem in logspace: We should remember only two counters (2logn) and try to each possibility of nodes in first and last layer (it gives $O(n^2)$ possiblities, every of them we check one by one, so we use only logspace memory to remember two counters. However, I am not sure if you meant this thing that I described above. – user54001 May 3 '17 at 10:00

Reingold's result gives a logspace algorithm, but reachability on undirected grid graphs was show to be in $$L$$ by Blum and Kozen about 30 years prior: