<p>Barrington's theorem shows that <strong>polynomial size, bounded width</strong> 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 <strong>any</strong> 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 <strong>do</strong> 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. <a href="http://dl.acm.org/citation.cfm?doid=48014.63138">this paper</a>).</p>

<p>There is an <a href="http://link.springer.com/book/10.1007/978-3-642-24508-4/page/1">excellent book</a> by Jukna which studies different types of branching programs in depth.</p>

CC BY-SA 3.0
2013-09-29T00:00:01.520Z
2013-09-29T00:20:55.997Z
2013-09-29T00:20:55.997Z
Robert Robere
<p>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?</p>

CC BY-SA 3.0
2013-09-28T22:32:06.153Z
Small correction: polysize branching programs exist for all languages in L/poly (http://en.wikipedia.org/wiki/L/poly). Barrington's theorem says something different (about fixed width BP).
cryptocat
CC BY-SA 3.0
2013-09-28T23:02:01.060Z
Do the results in Section 7 of A. A. Razborov, [Lower bounds for deterministic and nondeterministic branching programs](http://people.cs.uchicago.edu/~razborov/files/fct.pdf) (Proc. FCT, 1991) help?
David Richerby
<cc.complexity-theory><circuit-complexity>
What functions can read-once branching programs compute?
Akshay
# What functions can read-once branching programs compute?

(Asked by: username_0 on 2013-09-28)

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?

**Tags:** cc.complexity-theory, circuit-complexity
> **Comments:**
> **username_1**: Small correction: polysize branching programs exist for all languages in L/poly (http://en.wikipedia.org/wiki/L/poly). Barrington's theorem says something different (about fixed width BP).  
> **username_2**: Do the results in Section 7 of A. A. Razborov, [Lower bounds for deterministic and nondeterministic branching programs](http://people.cs.uchicago.edu/~razborov/files/fct.pdf) (Proc. FCT, 1991) help?  

---

## 1 answers

### Answer by username_3 on 2013-09-29. Score: 9 | Accepted answer

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](http://dl.acm.org/citation.cfm?doid=48014.63138)).

There is an [excellent book](http://link.springer.com/book/10.1007/978-3-642-24508-4/page/1) by Jukna which studies different types of branching programs in depth.


---

