<p>Perhaps you'd be interested in switching networks. According to Potechin's <em><a href="http://eccc.hpi-web.de/report/2009/142/download/" rel="nofollow">Bounds on monotone switching networks for directed connectivity</a></em>, 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.</p>

<p>Potechin has been working on separating L and NL, but so far his method only works for monotone networks. See also his <a href="http://dl.acm.org/citation.cfm?id=2214024" rel="nofollow">STOC 2012 paper</a> with Siu Man Chan. (More papers are on the way.)</p>

CC BY-SA 3.0
2012-09-04T02:04:02.140Z
2012-09-04T02:04:02.140Z
Yuval Filmus
<p>If I'm understanding your question correctly, there is probably no way to do it. While there must be a nondeterministic branching program for the problem (since it is in $\bf NL$), you couldn't necessarily find it if all you know is an $\bf NP$ algorithm for the problem. </p>

<p>And it seems that the one-way constraint on the nondeterministic bitstream would block any attempt to build a universal Levin-style algorithm for $\bf NL$.</p>

CC BY-SA 3.0
2012-09-03T19:52:08.403Z
2012-09-03T19:52:08.403Z
Ben Standeven
<p>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.</p>

<p>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. </p>

<p><strong>Question:</strong></p>

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

<hr>

<p>Reference:</p>

<p>N.Pippenger and M.Fischer, Relations among complexity measures, J of ACM, 1979.</p>

CC BY-SA 3.0
2012-05-24T18:28:54.717Z
What have you checked so far? What is the motivation behind the question?
Kaveh
CC BY-SA 3.0
2012-05-24T20:06:50.553Z
You have not accepted any answers to your questions, and that is considered not nice.  Please check [How do I ask questions here?](http://cstheory.stackexchange.com/faq#howtoask) in the FAQ.
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-25T07:08:23.543Z
Kaveh, thank you for your helpful comments. I wrote a motivation of my question, and edited the title to be appropriate for my motivations. I am very  greatful if you understand this motivation.
Jeigh
CC BY-SA 3.0
2012-05-26T19:04:30.383Z
A reference to Pippenger's result might  be useful here.
Suresh Venkat
CC BY-SA 3.0
2012-06-01T02:54:37.780Z
Venkat, I added the refference.
Jeigh
CC BY-SA 3.0
2012-06-01T04:09:47.430Z
It is still not clear for me what you are asking exactly, e.g. I don't understand the following: "Is there a Nondeterministic polynomial size branching program solving a NLcomplete problem if we take a Nondeterministic Turing Machine solving the same problem". If you want related results you may want to check Steve Cook and his colleagues work and ideas about using branching programs to separate $\mathsf{L}$ (and $\mathsf{NL}$) from $\mathsf{P}$ like "[Pebbles and Branching Programs for Tree Evaluation](http://arxiv.org/abs/1005.2642)". You can also find some slides on his webpage.
Kaveh
CC BY-SA 3.0
2012-09-04T12:19:34.610Z
Too many typos in the question, so I tried to edit a bit. However I still don't understand the meaning of the main question. @Jeigh could you please edit your question?
Dai Le
<cc.complexity-theory><complexity-classes><advice-and-nonuniformity>
Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project
Jeigh
# Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project

(Asked by: username_0 on 2012-05-24)

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.

**Tags:** cc.complexity-theory, complexity-classes, advice-and-nonuniformity

> **Comments:**
> **username_1**: What have you checked so far? What is the motivation behind the question?  
> **username_2**: You have not accepted any answers to your questions, and that is considered not nice.  Please check [How do I ask questions here?](http://cstheory.stackexchange.com/faq#howtoask) in the FAQ.  
> **username_0**: username_1, thank you for your helpful comments. I wrote a motivation of my question, and edited the title to be appropriate for my motivations. I am very  greatful if you understand this motivation.  
> **username_3**: A reference to Pippenger's result might  be useful here.  
> **username_0**: Venkat, I added the refference.  
> **username_1**: It is still not clear for me what you are asking exactly, e.g. I don't understand the following: "Is there a Nondeterministic polynomial size branching program solving a NLcomplete problem if we take a Nondeterministic Turing Machine solving the same problem". If you want related results you may want to check Steve Cook and his colleagues work and ideas about using branching programs to separate $\mathsf{L}$ (and $\mathsf{NL}$) from $\mathsf{P}$ like "[Pebbles and Branching Programs for Tree Evaluation](http://arxiv.org/abs/1005.2642)". You can also find some slides on his webpage.  
> **username_4**: Too many typos in the question, so I tried to edit a bit. However I still don't understand the meaning of the main question. @username_0 could you please edit your question?  

---

## 2 answers

### Answer by username_5 on 2012-09-04. Score: 4

Perhaps you'd be interested in switching networks. According to Potechin's *[Bounds on monotone switching networks for directed connectivity](http://eccc.hpi-web.de/report/2009/142/download/)*, 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](http://dl.acm.org/citation.cfm?id=2214024) with Siu Man Chan. (More papers are on the way.)


---

### Answer by username_6 on 2012-09-03. Score: 0

If I'm understanding your question correctly, there is probably no way to do it. While there must be a nondeterministic branching program for the problem (since it is in $\bf NL$), you couldn't necessarily find it if all you know is an $\bf NP$ algorithm for the problem.

And it seems that the one-way constraint on the nondeterministic bitstream would block any attempt to build a universal Levin-style algorithm for $\bf NL$.


---

