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.’

Bibliographie

[1] Andreev A. E., “Sintez skhem iz funktsionalnykh elementov v polnykh monotonnykh bazisakh”, Matem. voprosy kibern., 1 (1985), 114–139 | MR

[2] Korobkov V. K., “O monotonnykh funktsiyakh algebry logiki”, Probl. kibern., 13 (1965), 5–28 | MR | Zbl

[3] Korshunov A. D., “O chisle monotonnykh bulevykh funktsii”, Probl. kibern., 38 (1965), 5–108 | MR

[4] Lupanov O. B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Probl. kibern., 14 (1965), 31–110 | MR | Zbl

[5] Nechiporuk E. I., “O ventilnykh skhemakh”, Tezisy dokl. Mezhdunarodnogo simpoziuma po teorii releinykh skhem i konechnykh avtomatov, Moskva, 1962, 42–43

[6] Redkin N. P., “O realizatsii monotonnykh bulevykh funktsii kontaktnymi skhemami”, Tezisy dokl. 4-i Vsesoyuznoi konferentsii po problemam teoreticheskoi kibernetiki, Novosibirsk, 1977, 180–181

[7] Redkin N. P., “O realizatsii monotonnykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Probl. kibern., 36 (1979), 87–110 | MR

[8] Reznik V. I., “O realizatsii monotonnykh funktsii skhemami iz funktsionalnykh elementov”, DAN SSSR, 139:3 (1961), 566–569 | MR | Zbl

[9] Ugolnikov A. B., “O realizatsii monotonnykh funktsii skhemami iz funktsionalnykh elementov”, Probl. kibern., 31 (1976), 167–185 | MR

[10] Chashkin A. V., “O srednem vremeni vychisleniya znachenii bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:1 (1997), 60–78 | MR | Zbl

[11] Chashkin A. V., “Ob odnom metode vychisleniya chastichnykh bulevykh funktsii”, Matem. voprosy kibern., 12 (2004), 231–246

[12] Chashkin A. V., “O slozhnosti realizatsii bulevykh funktsii frmulami”, Diskretnyi analiz i issledovanie operatsii, 12:2 (2005), 56–72 | MR

[13] Yablonskii S. V., “O klassakh funktsii algebry logiki, dopuskayuschikh prostuyu skhemnuyu realizatsiyu”, Uspekhi matem. nauk, 12:6 (1957), 189–196 | MR | Zbl

[14] Hansel G., “Sur le nombre des fonctions booléennes monotones de $n$ variables”, C. R. Acad. Sci. Paris, 262 (1966), 1088–1099 | MR

[15] Kleitman D., “On Dedekind's problem: the number of monotone Boolean functions”, Proc. Amer. Math. Soc., 21:3 (1969), 677–682 | DOI | MR | Zbl

[16] Pippenger N., “The complexity of monotone-boolean functions”, Math. Syst. Theory, 11 (1978), 289–316 | DOI | MR | Zbl