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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ What have you checked so far? What is the motivation behind the question? $\endgroup$
    – Kaveh
    Commented May 24, 2012 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
    Commented May 24, 2012 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
    Commented May 25, 2012 at 7:08
  • $\begingroup$ A reference to Pippenger's result might be useful here. $\endgroup$
    – Suresh Venkat
    Commented May 26, 2012 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
    Commented Sep 4, 2012 at 12:19

2 Answers 2

Reset to default
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.)

Improve this answer
$\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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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