Конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова

Россия, Новосибирск, Академгородок, 8 - 11 октября 2001 года,
(номер государственной регистрации 0320300063)

Тезисы докладов

Математическая кибернетика

Нижние оценки сложности ветвящихся программ

Окольнишникова Е.А.

Институт математики им. С.Л. Соболева (Новосибирск)

The problem of finding nontrivial lower bounds on the complexity of "well-defined" Boolean functions is one of the most important problems in the mathematical theory of complexity. In the paper the computation of characteristic functions of Reed-Muller codes by nondeterministic branching programs is considered.

Дополнительные материалы: HTML
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии

[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации 06-Jul-2012 (11:45:21)