Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project Boolean circuit is used to measure  time in a nonuniform way, which Pippenger showed the relation between a time complexity of uniform model (Turing Machines) and size complexity of boolean circuits.  In the theory of space complexity, branching programs are considered to measure nonuniform space complexity.

I want a survey to answer the following question. My motivation came from the state of the art of attempts for separation between NL and L, that is , proving L vs NL problem. I would like to know whether there is any analogous approach for proving separation between  time complexity classes (deriving circuit lower bounds is useful for separation of time complexity classes because this approach is supported by Pippenger's theorem).  Thus I would like to know whether there is an analogue of Pippernger's theorem which would support non-uniform approaches for separation of the space complexity classes like circuit lower bounds. 

Question:


  Is there a Nondeterministic polynomial size branching program solving
  an NL-complete problem  if we take a Nondeterministic Turing Machine
  solving the same problem ?




Reference:

N.Pippenger and M.Fischer, Relations among complexity measures, J of ACM, 1979.
Perhaps you'd be interested in switching networks. According to Potechin's Bounds on monotone switching networks for directed connectivity, one way to separate L from NL is to show that there is no polysize switching network for directed connectivity. There is in fact a (trivial) polysize switching-and-rectifier network for directed connectivity. The difference between the two models is that the former is undirected and the latter directed.

Potechin has been working on separating L and NL, but so far his method only works for monotone networks. See also his STOC 2012 paper with Siu Man Chan. (More papers are on the way.)