Том 14, серия 1, номер 3, 2007 г., Стр. 31-39

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

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

Васильев А. В. ¹
1. Казанский государственный университет,
ул. Кремлевская, 18, 420008 Казань, Россия
е-mail: vaslo@mail.ru

Статья поступила 20 октября 2006 г.
Исправленный вариант — 18 мая 2007 г.