Детерминированные и вероятностные без ошибки упорядоченные один раз читающие бинарные программы равномощны

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