О функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида

Дэвид М. Баррингтон доказал совпадение класса функций, реализуемых схемами из функциональных элементов логарифмической глубины NC$^1$, с классом функций, представимых ветвящимися программами константной ширины и полиномиальной длины BWBP.
В статье уточняется структура ветвящихся программ, получаемых предложенным Баррингтоном методом. А именно, доказывается, что с помощью $k$-OBDD полиномиальной сложности и ширины 5 можно реализовать все функции из класса NC$^1$ и только их. Это утверждение можно переформулировать следующим образом: poly$(n)$-OBDD$_5$ = NC$^1$.
Библ. 4.