Upper bounds on the formula size of symmetric Boolean functions

I. S. Sergeev

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2014), pp. 38-52.

Résumé

It is proved that complexity of implementation of the counting function of $n$ Boolean variables with binary formulae is at most $n^{3.03}$ and is at most $n^{4.47}$ with respect to DeMorgan formulae. Hence, the same bounds hold for the formula size of any threshold symmetric function of $n$ variables, particularly, for majority function. The following bounds are proved for the formula size of any symmetric Boolean function of $n$ variables: $n^{3.04}$ with respect to binary formulae and $n^{4.48}$ with respect to DeMorgan formulae. A proof is based on modular arithmetic.

Détail

Keywords: formula size, symmetric Boolean functions, majority function
Mots-clés : multiplication.

Bibliographie

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[2] Nigmatullin R. G., Slozhnost bulevykh funktsii, Nauka, M., 1991 | MR | Zbl

[3] Chashkin A. V., Diskretnaya matematika, Akademiya, M., 2012

[4] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1986 | MR

[5] Dunne P. E., The complexity of Boolean networks, Academic Press, San Diego, 1988 | MR | Zbl

[6] Jukna S., Boolean function complexity, Springer-Verlag, Berlin–Heidelberg, 2012 | MR | Zbl

[7] Khrapchenko V. M., “O slozhnosti realizatsii simmetricheskikh funktsii algebry logiki formulami v konechnykh bazisakh”, Problemy kibernetiki, 31, Nauka, M., 1976, 231–234

[8] Cherukhin D. Yu., “Nizhnie otsenki formulnoi slozhnosti simmetricheskikh bulevykh funktsii”, Diskr. analiz i issled. oper. Ser. 1, 7:3 (2000), 86–98 | MR | Zbl

[9] Khrapchenko V. M., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti $\pi$-skhem”, Matem. zametki, 10:1 (1971), 83–92 | MR | Zbl

[10] Fischer M. J., Meyer A. R., Paterson M. S., “$\Omega(n\log n)$ lower bounds on length of Boolean formulas”, SIAM J. Comput., 11:3 (1982), 416–427 | DOI | MR | Zbl

[11] Sergeev I. S., Upper bounds for the formula size of the majority function, 2012, [tam zhe russkii perevod], arXiv: 1208.3874

[12] Paterson M., Zwick U., “Shallow circuits and concise formulae for multiple addition and multiplication”, Comput. Complexity, 3:3 (1993), 262–291 | DOI | MR | Zbl

[13] Peterson G. L., An upper bound on the size of formulae for symmetric Boolean function, Tech. Report 78-03-01, Univ. Washington, 1978

[14] Khrapchenko V. M., “O slozhnosti realizatsii simmetricheskikh funktsii formulami”, Matem. zametki, 11:1 (1972), 109–120 | MR | Zbl

[15] Paterson M. S., Pippenger N., Zwick U., “Optimal carry save networks”, Boolean function complexity, LMS Lecture Notes Series, 169, Cambridge University Press, 1992, 174–201 | MR

[16] Paterson M. S., Pippenger N., Zwick U., “Faster circuits and shorter formulae for multiple addition, multiplication and symmetric Boolean functions”, Proc. 31st IEEE Symp. Found. Comput. Sci., 1990, 642–650

[17] Stolyarov G. K., Sposob parallelnogo umnozheniya v tsifrovykh vychislitelnykh mashinakh i ustroistvo dlya osuschestvleniya sposoba, Avt. svid-vo kl. 42 t 14, No 126668, 1960

[18] Stockmeyer L. J., “On the combinational complexity of certain symmetric Boolean functions”, Math. Syst. Theory, 10:4 (1977), 323–336 | MR | Zbl

[19] Demenkov E., Kojevnikov A., Kulikov A., Yaroslavtsev G., “New upper bounds on the Boolean circuit complexity of symmetric functions”, Inf. Proc. Letters, 110:7 (2010), 264–267 | DOI | MR | Zbl

[20] Lupanov O. B., “K voprosu o realizatsii simmetricheskikh funktsii algebry logiki kontaktnymi skhemami”, Problemy kibernetiki, 15, Nauka, M., 1965, 85–99 | MR

[21] Gashkov S. B., Zanimatelnaya kompyuternaya arifmetika. Bystrye algoritmy operatsii s chislami i mnogochlenami, Librokom, M., 2012