Том 8, серия 1, номер 4, 2001 г., Стр. 76-102
УДК 519.714.4 + 519.725
Е. А. Окольнишникова
Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами
Аннотация:
Предложен метод получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами. Получена нелинейная нижняя оценка$\Omega(n\log n/\log\log n)$ для сложности реализации характеристических функций кодов Рида–Маллера такими программами.
Ил. 2, библиогр. 13.
Околънишникова Е. А. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 28 августа 2001 г.
