# 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.

• What have you checked so far? What is the motivation behind the question? – Kaveh May 24 '12 at 18:28
• You have not accepted any answers to your questions, and that is considered not nice. Please check How do I ask questions here? in the FAQ. – Tsuyoshi Ito May 24 '12 at 20:06
• 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 May 25 '12 at 7:08
• A reference to Pippenger's result might be useful here. – Suresh Venkat May 26 '12 at 19:04
• 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 Sep 4 '12 at 12:19

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$.