О сложности один раз читающих вероятностных программ

Упорядоченные один раз читающие ветвящиеся программы представляют собой удобное средство описания логических схем, булевых функций. Вместе с тем не только детерминированные, но и вероятностные с ограничением на ошибку упорядоченные один раз читающие ветвящиеся программы имеют неприемлемо большой (экспоненциальный) размер для ряда известных функций. Для вероятностных один раз читающих ветвящихся программ экспоненциальные нижние оценки сложности известны лишь при очень сильных ограничениях. В данной статье эти ограничения частично снимаются за счет перехода к ветвящимся программам, определяемым графом порядка. Для этих вычислительных моделей удается доказать экспоненциальные нижние оценки сложности.