Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696)

The main result is the proof of the equivalence of \(NC^ 1\) (the class of languages recognizable by fan-in two, logarithmic depth circuits) and of \({\mathcal P}_{bw-BP}\) (the class of languages recognizable by bounded width, polynomial size branching programs) which is one of the most important and surprising results in complexity theory of the last years. In more detail, it is proved that width-5 braching programs as well as width-4 circuits of polynomial size recognize exactly nonuniform \({\mathcal N}{\mathcal C}^ 1.\) Generalizing the method of proof the author also shows that the word problem for any fixed nonsolvable groups is complete for \({\mathcal N}{\mathcal C}^ 1\) under \({\mathcal A}{\mathcal C}^ 0\) reductions. A list of open problems and a survey of recent progress round off this important paper.