TR16-155 Authors: Vaibhav Krishan, Nutan Limaye

Publication: 11th October 2016 13:10

Downloads: 1071

Keywords:

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.