2
$\begingroup$

Barrington's Theorem gives us that polynomial size and bounded width Branching programs can compute exactly functions in $NC_1$, are there any results known about read-once BPs - bounded width and polynomial size?

$\endgroup$
7
$\begingroup$

Barrington's theorem shows that polynomial size, bounded width branching programs compute exactly the languages in $NC^1$. (Specifically, he shows this for branching programs with width at least 5, and a later result shows that 5 is necessary to capture $NC^1$). However, it's easy to see that any function is computable by an exponential size, read-once branching program (just take a decision tree which branches on every variable and outputs the truth-table of the function). If we wanted to focus on, say, polynomial size, read-once branching programs, then nothing is really known in terms of a standard complexity class. The "bounded replication" classes of branching programs (i.e. branching programs with a restriction on the number of times variables appear) don't really offer themselves well to such characterizations. Rather, the complexity classes for which we do have branching program characterizations are natural, given the model (i.e. like $L/poly$) or given via an algebraic approach, like Barrington's theorem or related results (e.g. this paper).

There is an excellent book by Jukna which studies different types of branching programs in depth.

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