О средней монотонной сложности булевых функций

Исследуется средняя сложность вычисления булевых функций неветвящимися монотонными программами с условной остановкой. Показано, что существуют такие $n$-местные булевы функции, что отношение средней монотонной сложности этих функций к обычной средней сложности равно $\Omega(\sqrt{2^n/n}\,)$. Также показано, что средняя монотонная сложность линейной функции с точностью до постоянного множителя равна $n\log_2 n$. Приведен пример линейного оператора, средняя монотонная сложность которого с точностью до постоянного множителя равна $n^2$.