BOUNDED WIDTH BRANCHING PROGRAMS
David A. Mix Barrington · DSpace@MIT (Massachusetts Institute of Technology) · 1986
We examine the branching program model of computation and in particular the classes of languages which can be recognized when the width of the programs is bounded by a constant. After slightly revising the framework of definitions to sharpen analogies with other models, we prove that width 5 polynomial size branching programs can recognize exactly the parallel complexity class NC1, refuting a conjecture of Borodin et al. in [BDFP83].