Том 11, серия 1, номер 4, 2004 г., Стр. 68-80
УДК 519.7
А. В. Чашкин
О средней монотонной сложности булевых функций
Аннотация:
Исследуется средняя сложность вычисления булевых функций неветвящимися монотонными программами с условной остановкой. Показано, что существуют такие$n$ -местные булевы функции, что отношение средней монотонной сложности этих функций к обычной средней сложности равно$\Omega(\sqrt{2^n/n}\,)$ . Также показано, что средняя монотонная сложность линейной функции с точностью до постоянного множителя равна$n\log_2 n$ . Приведен пример линейного оператора, средняя монотонная сложность которого с точностью до постоянного множителя равна$n^2$ .
Чашкин А. В. 1
1. МГУ, мех.-мат. факультет, Воробьевы горы,
119992 Москва, Россия
е-mail: chash@online.ru
Статья поступила 15 апреля 2004 г.
