On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates

I. S. Sergeev

Diskretnaya Matematika, Tome 30 (2018) no. 2, pp. 120-137.

Résumé

We obtain estimates for the complexity of the implementation of $n$-place Boolean functions by circuits and formulas built of unbounded fan-in conjunction and disjunction gates and either negation gates or negations of variables as inputs. Restrictions on the depth of circuits and formulas are imposed. In a number of cases, the estimates obtained in the paper are shown to be asymptotically sharp. In particular, for the complexity of circuits with variables and their negations on inputs, the Shannon function is asymptotically estimated as $2\cdot2^{n/2}$; this estimate is attained on depth-3 circuits.

Détail

Keywords: bounded-depth circuits, complexity, Boolean cube partitions.

Bibliographie

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

[2] Jukna S., Boolean function complexity, Springer-Verlag, Berlin, Heidelberg, 2012, 618 pp. | MR | Zbl

[3] Wegener I., Complexity theory, Springer-Verlag, Berlin, Heidelberg, 2005, 308 pp. | Zbl

[4] Lupanov O. B., “O realizatsii funktsii algebry logiki formulami iz konechnykh klassov (formulami ogranichennoi glubiny) v bazise $\, \vee, \overline{\phantom{a}}\,$”, Problemy kibernetiki, 6, Fizmatlit, M., 1961, 5–14

[5] Lupanov O. B., “O realizatsii funktsii algebry logiki skhemami iz funktsionalnykh elementov «ogranichennoi glubiny» v bazise $\, \vee, \overline{\phantom{a}}\,$”, Sb. rabot po matematicheskoi kibernetike, v. 2, Izd-vo VTs AN SSSR, M., 1977, 3–8

[6] Lozhkin S. A., Konovodov V. A., “On the synthesis and complexity of formulae with bounded depth of alternation”, Moscow University Computational Mathematics and Cybernetics, 36:2 (2012), 81–91 | DOI | MR | Zbl

[7] Dančík V., “Complexity of Boolean functions over bases with unbounded fan-in gates”, Inform. Proc. Letters, 57 (1996), 31–34 | DOI | MR | Zbl

[8] Nechiporuk E. I., “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 123–160 | MR

[9] Kasim-Zade O. M., “Obschaya verkhnyaya otsenka slozhnosti skhem v proizvolnom beskonechnom polnom bazise”, Vestnik Mosk. un-ta. Ser. 1. Matem. Mekh., 1997, no. 4, 59–61 | Zbl

[10] Nechiporuk E. I., “O sinteze skhem iz porogovykh elementov”, Problemy kibernetiki, 11, Nauka, M., 1964, 49–62 | MR

[11] Lupanov O. B., “O sinteze skhem iz porogovykh elementov”, Problemy kibernetiki, 26, Nauka, M., 1973, 109–140

[12] Zuev Yu. A., “Porogovye funktsii i porogovye predstavleniya bulevykh funktsii”, Matem. voprosy kibernetiki, 5, Fizmatlit, M., 1994, 5–61

[13] Lipatova A. E., “Ob odnom pokrytii mnozhestva dvoichnykh naborov i realizatsii kon'yunktsii kontaktnymi skhemami”, Matem. voprosy kibernetiki, 2, Nauka, M., 1989, 161–173 | MR

[14] Lupanov O. B., “O ventilnykh i kontaktno-ventilnykh skhemakh”, Doklady AN SSSR, 111:6 (1956), 1171–1174 | Zbl

[15] Kabatiansky G. A., Panchenko V. I., “Unit sphere packings and coverings of the Hamming space”, Problems of Information Transmission, 24:4 (1998) | MR

[16] Cooper J. N., Ellis R. B., Kahng A. B., “Asymmetric binary covering codes”, J. Comb. Theory, Ser. A, 100 (2002), 232–249 | DOI | MR | Zbl

[17] Chashkin A. V., Diskretnaya matematika., Akademiya, M., 2012, 352 pp.

[18] Zhuravlev Y. I., Kogan A. Y., “Realization of Boolean functions with a small number of zeros by disjunctive normal forms, and related problems”, Soviet Mathematics (Izvestiya VUZ. Matematika), 32 (1985), 771–774 | MR | Zbl