Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-155 | 10th October 2016 07:13

Isolation Lemma for Directed Reachability and NL vs. L


Authors: Vaibhav Krishan, Nutan Limaye
Publication: 11th October 2016 13:10
Downloads: 1302


In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a given directed graph with a source sink pair (s, t) then NL is contained in L/poly. By isolating a path we mean outputting a new graph on the same set of nodes such that exactly one s-t path from the original graph survives. Such an isolating procedure will naturally imply a UL/poly algorithm for reachability, but we prove that in fact this implies an L/poly algorithm.
We also prove a similar result for the class LogCFL.

ISSN 1433-8092 | Imprint