Том 11, серия 1, номер 2, 2004 г., Стр. 80-90

УДК 519.714
Р. Г. Мубаракзянов
Детерминированные и вероятностные без ошибки упорядоченные один раз читающие бинарные программы равномощны

Аннотация:
Приводится полное доказательство результата, представленного автором на Workshop on Computer Science and Information Technologies, CSIT'99 (Москва, январь 1999 г.). Доказывается, что упорядоченные один раз читающие бинарные программы (OBDD в англоязычной литературе) полиномиального размера, осуществляющие вероятностное вычисление без ошибки, вычисляют лишь простые функции для детерминированных OBDD. Данный факт не имеет места для один раз читающих бинарных программ, в которых порядок считывания переменных не фиксирован.

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

Статья поступила 16 июня 2003 г.