0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/SL_(complexity) $\endgroup$ – D.W. May 3 '17 at 1:10
  • $\begingroup$ 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. $\endgroup$ – user54001 May 3 '17 at 10:00
2
$\begingroup$

I can't post a comment, which would be more appropriate:

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:

M. Blum and D. Kozen. On the power of the compass (or, why mazes are easier to search than graphs). In IEEE Symposium on Foundations of Computer Science (FOCS), pages 132–142, 1978.

$\endgroup$
1
$\begingroup$

Your problem is an instance of USTCON, which is known to be solvable in log space, thanks to a result of Omer Reingold:

Undirected connectivity in log-space. Omer Reingold. Journal of the ACM, vol 55 no 4, Sept 2008.

Thus, that paper describes how to build a logspace deterministic Turing machine that does what you want.

$\endgroup$
  • 1
    $\begingroup$ I think that your proposition here is overkill here. Lets note that our graph is special (grid). Moreover, we are looking for path between layers. Of course, I understand that using your paper it is solved immediately. $\endgroup$ – user54001 May 6 '17 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy