-- Practice Final Questions
Question 2. Alan, Anusha
PATH is in SPACE(log^2n)
Let G be a graph with n nodes, let x and y be nodes of G and let i >=0. We say that PATH(x,y,i) holds if there is a path from x to y in G of length atmost 2^i.
We can compute reachability of any two nodes in G if we determine if PATH(x,y,log n) exists.
Input tape is the adjacency matrix. There are two other tapes other than input tape. Assume first tape has(x,y,i) already copied to it. The tape will store several tripes and (x,y,i) will be leftmost.
i. i=0, compute PATH(x,y,0) This is possible if x=y. if i=1, check whether there exists 1 edge between x and y. This can be done in log space.
ii. for i>0, we can compute PATH(x,y,i) with recursive algorithm.
For all nodes z check if PATH(x,z,i-1) and PATH(z,y,i-1) exists. We can generate each z in turn reusing space and perform the test. As there are n nodes, it takes log n bits to store z.
If there is a PATH(x,z,i), we replace (x,z,i-1) with (z,y,i-1)
At any gien time in computing PATH(x,y,logn) we have atmost log n many triples on the work tape and each triple takes atmost 3 log n which gives us O(log^2n) space.
Question 2. Alan, Anusha
PATH is in SPACE(log^2n)
Let G be a graph with n nodes, let x and y be nodes of G and let i >=0. We say that PATH(x,y,i) holds if there is a path from x to y in G of length atmost 2^i.
We can compute reachability of any two nodes in G if we determine if PATH(x,y,log n) exists.
Input tape is the adjacency matrix. There are two other tapes other than input tape. Assume first tape has(x,y,i) already copied to it. The tape will store several tripes and (x,y,i) will be leftmost.
i. i=0, compute PATH(x,y,0) This is possible if x=y. if i=1, check whether there exists 1 edge between x and y. This can be done in log space.
ii. for i>0, we can compute PATH(x,y,i) with recursive algorithm.
For all nodes z check if PATH(x,z,i-1) and PATH(z,y,i-1) exists. We can generate each z in turn reusing space and perform the test. As there are n nodes, it takes log n bits to store z.
If there is a PATH(x,z,i), we replace (x,z,i-1) with (z,y,i-1)
At any gien time in computing PATH(x,y,logn) we have atmost log n many triples on the work tape and each triple takes atmost 3 log n which gives us O(log^2n) space.