On the mean complexity of monotone functions

R. N. Zabaluev

Diskretnaya Matematika, Tome 18 (2006) no. 2, pp. 71-83

Résumé

We consider the complexity of realisation of the monotone functions by straight-line programs with conditional stop. It is shown that the mean complexity of each monotone function of $n$ variables does not exceed $a{2^n}/{n^{2}}(1+o(1))$ as $n\to\infty$, and the mean complexity of almost all monotone functions of $n$ variables is at least $b{2^n}/{n^{2}}(1+o(1))$ as $n\to\infty$, where $a$ and $b$ are constants.This research was supported by the Russian Foundation for Basic Research, grant 05–01–0099, by the Program of the President of the Russian Federation for support of leading scientific schools, grant 1807.2003.1, by the Program ‘Universities of Russia,’ grant 04.02.528, and by the Program of Fundamental Research of the Department of Mathematical Sciences of the Russian Academy of Sciences ‘Algebraic and Combinatorial Methods of Mathematical Cybernetics,’ project ‘Optimal synthesis of control circuits.’