3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What have you checked so far? What is the motivation behind the question? $\endgroup$ – Kaveh May 24 '12 at 18:28
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito May 24 '12 at 20:06
  • $\begingroup$ 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. $\endgroup$ – Jeigh May 25 '12 at 7:08
  • $\begingroup$ A reference to Pippenger's result might be useful here. $\endgroup$ – Suresh Venkat May 26 '12 at 19:04
  • 1
    $\begingroup$ 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? $\endgroup$ – Dai Le Sep 4 '12 at 12:19
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.