О СЛОЖНОСТИ ОДИН РАЗ ЧИТАЮЩИХ
ВЕРОЯТНОСТНЫХ  ПРОГРАММ
                             // Ученые записки КФУ. Физико-математические науки 2009 N2

Мубаракзянов Рустам Гамирович

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

О СЛОЖНОСТИ ОДИН РАЗ ЧИТАЮЩИХ ВЕРОЯТНОСТНЫХ ПРОГРАММ // Ученые записки КФУ. Физико-математические науки 2009 N2

Связанные документы (рекомендация CORE)

Новости проекта

Новости

Партнеры

Индексация