Homework answers / question archive / 1) A directed graph is strongly connected if, for all vertices it, v, there is a directed path from u to v

1) A directed graph is strongly connected if, for all vertices it, v, there is a directed path from u to v

Computer Science

Share With

1) A directed graph is strongly connected if, for all vertices it, v, there is a directed path from u to v. Prove that the following problem is NL-complete (under logspace reductions): {G (G is a strongly connected directed graph) You can use the fact that {(G,s, t) I G is a directed graph with a path from s to t) is NL-complete. Be sure to argue why your reduction can be done in logspace. 2. (a) Recall that RP is the set of languages L that can be solved in the following way by a PPT TM M: 
X E L Pr[M(x) = 1] > 1/2 x 0 L Pr[M(x) = 1] = 0 
So the only kind of "mistake" that M can make is to output 0 when the correct answer is 1. Take L to be in RP, with associated PPT TM M, and focus on a specific input length n. Define L„ = Ln {0, 1)„ — all the strings of length n in L. Show that there exists a random tape r' with the following property: at least half of x E L„ satisfy M(x; r.) = 1. In other words, one random taper' gives you the right answer for at least half of the inputs of length n. (b) Continuing to focus on L. and M defined above: Show that there is a set R. of random tapes, whose cardinality IRS is bounded by a polynomial in n (what polynomial in n? you should explain!), satisfying the following property: For all x e Ln, there is at least one r e R,, that satisfies M(x; r) = 1. In other words, there is a small set of random tapes, and one of those random tapes will yield the correct answer for all inputs of length n. From this you should be able to conclude that RP g P/poly.