Computational complexity of Boolean functions

A. D. Korshunov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 67 (2012) no. 1, pp. 93-165

Résumé

Boolean functions are among the fundamental objects of discrete mathematics, especially in those of its subdisciplines which fall under mathematical logic and mathematical cybernetics. The language of Boolean functions is convenient for describing the operation of many discrete systems such as contact networks, Boolean circuits, branching programs, and some others. An important parameter of discrete systems of this kind is their complexity. This characteristic has been actively investigated starting from Shannon's works. There is a large body of scientific literature presenting many fundamental results. The purpose of this survey is to give an account of the main results over the last sixty years related to the complexity of computation (realization) of Boolean functions by contact networks, Boolean circuits, and Boolean circuits without branching. Bibliography: 165 titles.

Détail

Keywords: basis, Boolean circuits, Boolean function, depth and delay of a Boolean circuit, disjunctive normal form, invariant classes of Boolean functions, contact network without zero chains, logical formulae, lower bounds for the complexity of circuits, series-parallel contact network, symmetric Boolean function, complexity of a circuit, partial Boolean function.
Mots-clés : cellular circuits

Bibliographie

[1] E. L. Post, The two-valued iterative systems of mathematical logic, Ann. of Math. Stud., 5, Princeton Univ. Press, Princeton, NJ, 1941, viii+122 pp. | MR | Zbl

[2] S. V. Yablonskii, G. P. Gavrilov, V. B. Kudryavtsev, Funktsii algebry logiki i klassy Posta, Nauka, M., 1966, 119 pp. | MR | Zbl

[3] R. G. Nigmatullin, Slozhnost bulevykh funktsii, Izd-vo Kazanskogo un-ta, Kazan, 1983, 208 pp. | MR

[4] J. E. Savage, The complexity of computing, Wiley, New York–London–Sydney, 1976, xiii+391 pp. ; D. E. Sevidzh, Slozhnost vychislenii, Faktorial, M., 1998 | MR | Zbl

[5] S. V. Yablonskii, “Ob algoritmicheskikh trudnostyakh sinteza minimalnykh kontaktnykh skhem”, Problemy kibernetiki, 2, Fizmatgiz, M., 1959, 75–121

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

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

[8] I. Wegener, The complexity of Boolean functions, Wiley-Teubner Ser. Comput. Sci., Wiley, Chichester; Teubner, Stuttgart, 1987, xii+457 pp. | MR | Zbl

[9] P. E. Dunne, The complexity of Boolean networks, APIC Stud. Data Processing, 29, Academic Press, London, 1988, xii+490 pp. | MR | Zbl

[10] R. G. Nigmatullin, Nizhnie otsenki slozhnosti i slozhnost universalnykh skhem, Izd-vo Kazanskogo un-ta, Kazan, 1990, 112 pp. | MR | Zbl

[11] P. Clote, E. Kranakis, Boolean functions and computation models, Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin, 2002, xiv+601 pp. | MR | Zbl

[12] W. H. Kautz, “A survey and assessment of progress in switching theory and logical design in the Soviet Union”, IEEE Trans. Electronic Computers, EC-15:2 (1966), 164–204 | DOI | MR

[13] Yu. L. Vasilev, V. V. Glagolev, “Metricheskie svoistva diz'yunktivnykh normalnykh form”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. I, Nauka, M., 1974, 99–148

[14] M. S. Paterson, “An introduction to Boolean function complexity”, Journées algorithmiques (École Norm. Sup., Paris, 1975), Astérisque, 38–39, 1976, 183–201 | MR | Zbl

[15] Yu. I. Zhuravlev, “Bulevykh funktsii metricheskaya teoriya”, Matematicheskaya entsiklopediya, v. 1, Izd-vo “Sovetskaya entsiklopediya”, M., 1977, 556–558

[16] V. M. Khrapchenko, “Nizhnie otsenki slozhnosti skhem iz funktsionalnykh elementov”, Kibernet. sb. Nov. ser., 21, Mir, M., 1984, 3–54 | MR

[17] A. A. Sapozhenko, I. P. Chukhrov, “Boolean function minimization in the class of disjunctive normal forms”, J. Soviet Math., 46:4 (1989), 2021–2052 | DOI | MR | Zbl | Zbl

[18] A. D. Korshunov, “Monotone Boolean functions”, Russian Math. Surveys, 58:5 (2003), 929–1001 | DOI | MR | Zbl

[19] C. E. Shannon, “A symbolic analysis of relay and switching circuits”, Trans. Amer. Inst. Electrical Engineers, 57:12 (1938), 713–723 ; K. Shennon, “Simvolicheskii analiz releinykh i pereklyuchatelnykh skhem”, K. Shennon. Raboty po teorii informatsii i kibernetike, IL, M., 1963, 9–45 | DOI

[20] C. Shannon, “The synthesis of two-terminal switching circuits”, Bell System Techn. J., 28:1 (1949), 59–98 ; K. Shennon, “Sintez dvukhpolyusnykh pereklyuchatelnykh skhem”, K. Shennon. Raboty po teorii informatsii i kibernetike, IL, M., 1963, 59–113 | MR

[21] G. N. Povarov, “Matematicheskaya teoriya sinteza kontaktnykh $(1,k)$-polyusnikov”, Dokl. AN SSSR, 100:5 (1955), 909–912

[22] G. N. Povarov, “Metod sinteza vychislitelnykh i upravlyayuschikh kontaktnykh skhem”, Avtomat. i telemekh., 18:2 (1957), 145–162

[23] O. B. Lupanov, “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, Fizmatgiz, M., 1963, 63–97

[24] E. F. Moore, “Minimal complete relay decoding networks”, IBM J. Res. and Develop., 4:5 (1960), 524–531 ; E. F. Mur, “Minimalnye polnostyu dekodiruyuschie kontaktnye skhemy”, Kibernet. sb., 6, IL, M., 1963, 139–152 | DOI | MR

[25] A. D. Korshunov, “O nizhnikh otsenkakh slozhnosti kontaktnykh skhem, realizuyuschikh poparno ortogonalnye funktsii algebry logiki”, Diskretnyi analiz, 2, In-t matematiki SO AN SSSR, Novosibirsk, 1964, 42–47

[26] N. P. Redkin, “O realizatsii sistem kon'yunktsii kontaktnymi skhemami”, Problemy kibernetiki, 30, Nauka, M., 1975, 263–276 | MR

[27] S. A. Lozhkin, M. A. Koshkin, “O slozhnosti realizatsii nekotorykh sistem funktsii algebry logiki kontaktnymi i obobschennymi kontaktnymi skhemami”, Matematicheskie voprosy kibernetiki, 3, Fizmatlit, M., 1991, 257–285 | MR

[28] Kh. A. Madatyan, “Sintez kontaktnykh skhem ogranichennoi shiriny”, Problemy kibernetiki, 14, Nauka, M., 1965, 301–307

[29] S. A. Lozhkin, “On the synthesis of oriented switching circuits”, Moscow Univ. Comput. Math. Cybern., 1995, no. 2, 32–37 | Zbl

[30] J. Riordan, C. E. Shannon, “The number of two-terminal series-parallel networks”, J. Math. Phys. Mass. Inst. Tech., 21:2 (1942), 83–93 ; Dzh. Riodan, K. Shennon, “Chislo dvukhpolyusnykh parallelno-posledovatelnykh setei”, K. Shennon. Raboty po teorii informatsii i kibernetike, IL, M., 1963, 46–58 | MR

[31] O. B. Lupanov, “Ob odnom metode sinteza skhem”, Izv. vuzov. Radiofizika, 1:1 (1958), 120–140

[32] O. B. Lupanov, “O slozhnosti realizatsii funktsii algebry logiki formulami”, Problemy kibernetiki, 3, Fizmatgiz, M., 1960, 61–80

[33] O. B. Lupanov, “O realizatsii funktsii algebry logiki formulami ogranichennoi glubiny v bazise $\,\vee,{}^-$”, Problemy kibernetiki, 6, Fizmatgiz, M., 1961, 5–14

[34] E. A. Kondrateva, “Ob universalnykh $\pi$-setyakh dlya funktsii algebry logiki ot $n$ peremennykh”, Problemy kibernetiki, 14, Nauka, M., 1965, 5–16

[35] O. A. Zadorozhnyuk, “O kontaktnykh skhemakh iz kletochnykh elementov”, Matematicheskie voprosy kibernetiki, 6, Fizmatlit, M., 1996, 257–280 | MR

[36] O. B. Lupanov, “The complexity of the universal parallel-sequential network of depth 3”, Proc. Steklov Inst. Math., 133 (1977), 127–132 | MR | Zbl | Zbl

[37] E. V. Sherisheva, “Postroenie universalnykh kontaktnykh skhem”, Problemy kibernetiki, 18, Nauka, M., 1967, 303–312

[38] F. Ya. Vetukhnovskii, “Ob otsenkakh chisla ploskikh grafov”, Dokl. AN SSSR, 142:1 (1962), 50–53

[39] A. D. Korshunov, “Ob asimptoticheskikh otsenkakh slozhnosti nekotorykh klassov kontaktnykh skhem”, Kibernetika, 1965, no. 2, 18–28 | Zbl

[40] Yu. G. Tarazevich, “On the complexity of the realization of multipoles by means of plane contact circuits”, Moscow Univ. Mech. Bull., 47:6 (1992), 20–22 | MR | Zbl

[41] A. K. Pulatov, “O vliyanii nulevykh tsepei na slozhnost realizatsii bulevykh funktsii kontaktnymi skhemami”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, Diskretnyi analiz, 30, In-t matematiki SO AN SSSR, Novosibirsk, 1977, 30–37 | MR

[42] S. V. Zdobnov, “O slozhnosti lineinoi funktsii v klasse $\pi$-skhem bez nulevykh tsepei”, Kombinatorno-algebraicheskie metody i ikh primenenie, Gorkovskii un-t, Gorkii, 1987, 27–34

[43] S. V. Zdobnov, “Algoritm sinteza minimalnykh $\pi$-skhem bez nulevykh tsepei, realizuyuschikh kharakteristicheskie funktsii lineinykh kodov”, Veroyatnostnye metody i kibernetika, 23, Izd-vo Kazanskogo un-ta, Kazan, 1987, 87–97 | MR

[44] S. V. Zdobnov, “O slozhnosti realizatsii kodovykh funktsii v klasse kontaktnykh skhem bez nulevykh tsepei”, Metody diskretnogo analiza v issledovanii funktsionalnykh sistem, Metody diskretnogo analiza, 47, In-t matematiki SO AN SSSR, Novosibirsk, 1988, 47–60 | MR

[45] S. V. Zdobnov, “Nizhnyaya otsenka funktsii Shennona dlya kontaktnykh skhem bez nulevykh tsepei”, Metody diskretnogo analiza v izuchenii bulevykh funktsii i grafov, Metody diskretnogo analiza, 48, In-t matematiki SO AN SSSR, Novosibirsk, 1989, 3–16 | MR

[46] S. E. Kuznetsov, “Circuits of functional elements without zero chains in the basis $\{\,\vee,-\}$”, Soviet Math., 25:5 (1981), 62–73 | MR | Zbl

[47] S. E. Kuznetsov, “Nizhnyaya otsenka funktsii Shennona dlya $\pi$-skhem bez nulevykh tsepei”, Metody diskretnogo analiza v izuchenii bulevykh funktsii i grafov, Metody diskretnogo analiza, 37, In-t matematiki SO AN SSSR, Novosibirsk, 1981, 51–64

[48] I. O. Sokolov, “Upper bounds on the complexity of the realization of characteristic functions of group codes by switching circuits without zero chains”, Discrete Math. Appl., 5:2 (1995), 137–148 | MR | Zbl

[49] A. D. Korshunov, “Ob asimptoticheskikh otsenkakh slozhnosti kontaktnykh skhem zadannoi stepeni”, Diskretnyi analiz, 5, In-t matematiki SO AN SSSR, Novosibirsk, 1965, 35–67

[50] V. M. Khrapchenko, “Complexity of the realization of a linear function in the class of $\Pi$-circuits”, Math. Notes, 9:1 (1971), 21–23 | DOI | MR | Zbl | Zbl

[51] S. V. Yablonskii, “Realizatsiya lineinoi funktsii v klasse $\pi$-skhem”, Dokl. AN SSSR, 94:5 (1954), 805–806 | MR | Zbl

[52] K. L. Rychkov, “Modifikatsiya metoda V. M. Khrapchenko i primenenie ee k otsenkam slozhnosti $\pi$-skhem dlya kodovykh funktsii”, Metody diskretnogo analiza v teorii grafov i skhem, Metody diskretnogo analiza, 42, In-t matematiki SO AN SSSR, Novosibirsk, 1985, 91–98

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

[54] C. Cardot, “Quelques résultats sur l'application de l'algèbre de Boole à la synthèse de circuits à relais”, Ann. Télécommun., 7:2 (1952), 75–84 | MR

[55] S. M. Vartanyan, “Novoe dokazatelstvo minimalnosti kontaktnoi skhemy, realizuyuschei lineinuyu funktsiyu”, Metody diskretnogo analiza v izuchenii realizatsii logicheskikh funktsii, Metody diskretnogo analiza, 41, In-t matematiki SO AN SSSR, Novosibirsk, 1984, 27–34 | MR

[56] Z. E. Koroleva, “Dokazatelstvo minimalnosti kontaktnykh skhem nekotorogo tipa”, Diskretnyi analiz, 14, In-t matematiki SO AN SSSR, Novosibirsk, 1969, 18–27 | MR

[57] Eh. I. Nechiporuk, “A Boolean function”, Soviet Math. Dokl., 7 (1966), 999–1000 | MR | Zbl

[58] L. Hodes, E. Specker, “Lengths of formulas and elimination of quantifiers. I”, Contributions to mathematical logic (Hannover, 1966), North-Holland, Amsterdam, 1968, 175–188 ; L. Khodes, E. Shpeker, “Dliny formul i isklyuchenie kvantorov”, Kibernet. sb. Nov. ser., 10, Mir, M., 1973, 99–113 | MR

[59] A. E. Andreev, “A method for obtaining more than quadratic effective lower estimates of complexity of $\pi$ schemes”, Moscow Univ. Math. Bull., 42:1 (1987), 63–66 | MR | Zbl | Zbl

[60] M. I. Grinchuk, “O slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktnymi skhemami”, Matematicheskie voprosy kibernetiki, 3, Fizmatlit, M., 1991, 77–114 | MR

[61] M. I. Grinchuk, “Nizhnyaya otsenka slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktnymi skhemami”, Matematicheskie voprosy kibernetiki, 4, Fizmatlit, M., 1992, 130–138 | MR

[62] Yu. I. Zhuravlev, “Ob otdelimosti podmnozhestv vershin $n$-mernogo edinichnogo kuba”, Sb. statei po matematicheskoi logike i ee prilozheniyam k nekotorym voprosam kibernetiki, Izd-vo AN SSSR, M., 1958, 143–157

[63] Yu. I. Zhuravlev, “Teoretiko-mnozhestvennye metody v algebre logiki”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 5–44

[64] Yu. I. Zhuravlev, “Algoritm postroeniya minimalnykh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, Nauka, M., 1974, 67–98

[65] Yu. I. Zhuravlev, “O razlichnykh ponyatiyakh minimalnosti d.n.f.”, Sib. matem. zhurn., 1:4 (1960), 609–610 | MR | Zbl

[66] Lin Sin-lyan, “O sravnenii slozhnostei minimalnykh i kratchaishikh diz'yunktivnykh normalnykh form dlya funktsii algebry logiki”, Problemy kibernetiki, 18, Nauka, M., 1967, 11–44 | MR

[67] V. V. Glagolev, “Estimate of the complexity of a reduced disjunctive normal form for almost all functions of the algebra of logic”, Soviet Math. Dokl., 5 (1965), 1302–1305 | MR | Zbl

[68] V. V. Glagolev, “Verkhnyaya otsenka slozhnosti minimalnoi d.n.f. dlya pochti vsekh funktsii algebry logiki”, Diskretnyi analiz, 5, In-t matematiki SO AN SSSR, Novosibirsk, 1965, 3–8 | MR

[69] A. D. Korshunov, “Verkhnyaya otsenka slozhnosti kratchaishikh d.n.f. pochti vsekh bulevykh funktsii”, Kibernetika, 1969, no. 6, 1–8

[70] A. A. Sapozhenko, “O slozhnosti diz'yunktivnykh normalnykh form, poluchaemykh s pomoschyu gradientnogo algoritma”, Diskretnyi analiz, 21, In-t matematiki SO AN SSSR, Novosibirsk, 1972, 62–71

[71] A. D. Korshunov, “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form bulevykh funktsii”, Metody diskretnogo analiza v izuchenii bulevykh funktsii i grafov, Metody diskretnogo analiza, 37, In-t matematiki SO AN SSSR, Novosibirsk, 1981, 9–41 | MR

[72] A. D. Korshunov, “O slozhnosti kratchaishikh diz'yunktivnykh normalnykh form sluchainykh bulevykh funktsii”, Metody diskretnogo analiza v optimizatsii upravlyayuschikh sistem, Metody diskretnogo analiza, 40, In-t matematiki SO AN SSSR, Novosibirsk, 1983, 25–53 | MR

[73] R. G. Nigmatullin, “Variatsionnyi printsip v algebre logiki”, Diskretnyi analiz, 6, In-t matematiki SO AN SSSR, Novosibirsk, 1967, 69–89 | MR

[74] A. E. Andreev, “On the synthesis of disjunctive normal forms which are close to minimal”, Soviet Math. Dokl., 27 (1983), 265–269 | MR | Zbl

[75] N. Pippenger, “The shortest disjunctive normal form of a random Boolean function”, Random Structures Algorithms, 22:2 (2003), 161–186 | DOI | MR | Zbl

[76] O. B. Lupanov, “O slozhnosti realizatsii funktsii algebry logiki releino-\allowbreakkontaktnymi skhemami”, Problemy kibernetiki, 11, Nauka, M., 1964, 25–47 | MR

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

[78] È. I. Nečiporuk, “Complexity of gating circuits which are realized by Boolean metrices with undetermined elements”, Soviet Phys. Dokl., 10 (1965), 591–593 | Zbl

[79] Eh. I. Nechiporuk, “Complexity of schemes in certain bases containing nontrivial elements with zero weights”, Soviet Math. Dokl., 2 (1961), 1087–1088 | Zbl

[80] A. A. Razborov, “Lower bounds of the complexity of symmetric Boolean functions of contact-rectifier circuits”, Math. Notes, 48:6 (1990), 1226–1234 | DOI | MR | Zbl | Zbl

[81] D. E. Muller, “Complexity in electronic switching circuits”, IRE Trans. Electron. Comput., EC-5:1 (1956), 15–19 | DOI

[82] A. B. Ugolnikov, “O realizatsii funktsii iz zamknutykh klassov skhemami iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 1, Fizmatlit, M., 1988, 89–113

[83] O. B. Lupanov, “O slozhnosti realizatsii stepenei bulevykh $(n,n)$-funktsii”, Matematicheskie voprosy kibernetiki, 12, Fizmatlit, M., 2003, 179–216

[84] O. B. Lupanov, “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, Nauka, M., 1965, 31–110 | MR

[85] L. A. Sholomov, “Informatsionnye svoistva funktsionalov slozhnosti dlya sistem nedoopredelennykh bulevykh funktsii”, Problemy kibernetiki, 34, Nauka, M., 1978, 133–150 | MR

[86] L. A. Sholomov, “O realizatsii nedoopredelennykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 21, Nauka, M., 1969, 215–226

[87] O. B. Lupanov, “Ob odnom klasse skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 7, Fizmatgiz, M., 1962, 61–114

[88] B. I. Finikov, “Ob odnom semeistve klassov funktsii algebry logiki i ikh realizatsii v klasse $\Pi$-skhem”, Dokl. AN SSSR, 115:2 (1957), 247–248 | MR | Zbl

[89] E. P. Lipatov, “Ob odnom sluchae neravnomernogo lokalnogo kodirovaniya”, Problemy kibernetiki, 26, Nauka, M., 1973, 95–107 | MR

[90] E. P. Lipatov, “Ob asimptoticheski optimalnom po slozhnosti i zaderzhke sinteze klassov vektor-funktsii”, Diskretnyi analiz, 24, In-t matematiki SO AN SSSR, Novosibirsk, 1974, 69–83 | MR

[91] N. Pippenger, “Information theory and the complexity of Boolean functions”, Math. Systems Theory, 10:2 (1976/77), 129–167 | DOI | MR

[92] L. A. Sholomov, “O funktsionalakh, kharakterizuyuschikh slozhnost sistem nedoopredelennykh bulevykh funktsii”, Problemy kibernetiki, 19, Nauka, M., 1967, 123–139

[93] L. A. Sholomov, “On the complexity of the sequential realization of partial Boolean functions by schemes”, J. Appl. Industr. Math., 2:2 (2008), 270–289 | DOI | MR

[94] A. A. Semenov, “Slozhnost priblizhennoi realizatsii bulevykh funktsii skhemami iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 5, Fizmatlit, M., 1994, 262–279

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

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

[97] N. A. Karpova, “O slozhnosti realizatsii funktsii algebry logiki v nekotorykh beskonechnykh bazisakh”, Metody diskretnogo analiza v teorii bulevykh funktsii i skhem, Metody diskretnogo analiza, 35, In-t matematiki SO AN SSSR, Novosibirsk, 1980, 9–14

[98] A. A. Markov, “Ob inversionnoi slozhnosti sistem funktsii”, Dokl. AN SSSR, 116:6 (1957), 917–919 | Zbl

[99] A. Markov, “On the inversion complexity of systems of Boolean functions”, Soviet Math. Dokl., 4 (1963), 694–696 | Zbl

[100] N. A. Karpova, “Some properties of Shannon functions”, Math. Notes, 8:5 (1970), 843–849 | DOI | MR | Zbl

[101] N. A. Karpova, “Nekotorye zamechaniya ob asimptoticheskom povedenii funktsii Shennona”, Problemy kibernetiki, 30, Nauka, M., 1975, 313–318 | MR

[102] M. I. Grinchuk, “O slozhnosti realizatsii bulevykh funktsii v trekh klassakh skhem v bazise, sostoyaschem iz vsekh simmetricheskikh funktsii”, Diskret. analiz i issled. oper., 3:1 (1996), 3–8 | MR | Zbl

[103] O. M. Kasim-Zade, “Ob odnom metode polucheniya otsenok slozhnosti nad beskonechnymi bazisami”, Matematicheskie voprosy kibernetiki, 11, Fizmatlit, M., 2002, 247–254 | MR

[104] O. M. Kasim-Zade, “Ob odnom metode polucheniya otsenok slozhnosti skhem nad proizvolnym beskonechnym bazisom”, Diskret. analiz i issled. oper. Cer. 1, 11:2 (2004), 41–65 | MR | Zbl

[105] N. A. Karpova, “O slozhnosti klassa skhem iz mnogopolyusnykh funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 7, Fizmatlit, M., 1998, 67–84 | MR

[106] N. A. Karpova, “O slozhnosti klassa skhem iz informatsionno bednykh mnogopolyusnykh elementov”, Matematicheskie voprosy kibernetiki, 15, Fizmatlit, M., 2006, 155–164

[107] S. B. Gashkov, “O glubine bulevykh funktsii”, Problemy kibernetiki, 34, Nauka, M., 1978, 265–268 | MR

[108] O. M. Kasim-Zade, “The depth of the Boolean functions in the realization by the schemes over an arbitrary basis”, Moscow Univ. Math. Bull., 62:1 (2007), 18–21 | MR | Zbl

[109] O. B. Lupanov, “O skhemakh iz funktsionalnykh elementov s zaderzhkami”, Problemy kibernetiki, 23, Nauka, M., 1970, 43–81 | MR

[110] V. M. Khrapchenko, “Razlichie i skhodstvo mezhdu zaderzhkoi i glubinoi”, Problemy kibernetiki, 35, Nauka, M., 1979, 141–168 | MR

[111] V. M. Khrapchenko, “New inequality relations between depth and delay”, Discrete Math. Appl., 5:6 (1995), 547–555 | Zbl

[112] V. M. Khrapchenko, “The fundamental difference between depth and delay”, Discrete Math. Appl., 18:4 (2008), 391–412 | DOI | MR | Zbl

[113] M. Vaincvaig, “On the power of networks of functional elements”, Soviet Phys. Dokl., 6 (1962), 454–547 | Zbl

[114] O. M. Kasim-Zade, “Ob odnovremennoi minimizatsii slozhnosti i moschnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 33, Nauka, M., 1978, 215–220 | MR

[115] O. M. Kasim-Zade, “Ob odnoi mere slozhnosti skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 38, Nauka, M., 1981, 117–179 | MR

[116] O. M. Kasim-Zade, “Ob odnoi mere aktivnosti skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 4, Fizmatlit, M., 1992, 218–228 | MR

[117] A. V. Kuznetsov, “O sredstvakh dlya obnaruzheniya nevyvodimosti ili nevyrazimosti”, Logicheskii vyvod, Nauka, M., 1979, 5–53

[118] O. M. Kasim-Zade, “O slozhnosti parametricheskikh predstavlenii bulevykh funktsii”, Matematicheskie voprosy kibernetiki, 7, Fizmatlit, M., 1998, 85–160 | MR

[119] A. D. Korshunov, “Ob otsenkakh slozhnosti skhem iz ob'emnykh funktsionalnykh elementov i ob'emnykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 19, Nauka, M., 1967, 275–283

[120] S. S. Kravtsov, “O realizatsii funktsii algebry logiki v odnom klasse skhem iz funktsionalnykh i kommutatsionnykh elementov”, Problemy kibernetiki, 19, Nauka, M., 1967, 285–292

[121] A. Albrekht, “O skhemakh iz kletochnykh avtomatov”, Problemy kibernetiki, 33, Nauka, M., 1978, 209–214

[122] N. A. Shkalikova, “O slozhnosti realizatsii nekotorykh funktsii kletochnymi avtomatami”, Sb. rabot po matematicheskoi kibernetike, 1, VTs AN SSSR, M., 1967, 102–115

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

[124] E. S. Gorelik, “O slozhnosti realizatsii elementarnykh kon'yunktsii i diz'yunktsii v bazise $\{x/y\}$”, Problemy kibernetiki, 26, Nauka, M., 1973, 27–36 | MR

[125] G. A. Kochergina, “O slozhnosti realizatsii elementarnykh kon'yunktsii i diz'yunktsii skhemami v nekotorykh polnykh bazisakh”, Matematicheskie voprosy kibernetiki, 11, Fizmatlit, M., 2002, 219–246 | MR

[126] C. P. Schnorr, “The combinational complexity of equivalence”, Theoret. Comput. Sci., 1:4 (1976), 289–295 ; K. P. Shnorr, “Kombinatsionnaya clozhnost ekvivalentnosti”, Kibernet. sb. Nov. ser., 16, Mir, M., 1979, 74–81 | DOI | MR | Zbl

[127] N. P. Redkin, “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23, Nauka, M., 1970, 83–101 | MR

[128] N. P. Redkin, “O minimalnoi realizatsii dvoichnogo summatora”, Problemy kibernetiki, 38, Nauka, M., 1981, 181–216 | MR

[129] I. S. Shkrebela, “On complexity of realisation of linear Boolean functions by circuits of functional elements over the basis $\{x\to y,\bar x\}$”, Discrete Math. Appl., 13:5 (2003), 483–496 | DOI | MR | Zbl

[130] E. I. Nechiporuk, “Ob odnoi bulevskoi matritse”, Problemy kibernetiki, 21, Nauka, M., 1969, 237–240 | MR

[131] L. H. Harper, “An $n\log n$ lower bound on synchronous combinational complexity”, Proc. Amer. Math. Soc., 64:2 (1977), 300–306 | MR | Zbl

[132] L. H. Harper, J. E. Savage, “Lower bounds on synchronous combinational complexity”, SIAM J. Comput., 8:2 (1979), 115–119 | DOI | MR | Zbl

[133] L. A. Sholomov, “Ob informatsionnoi slozhnosti zadach, svyazannykh s minimalnoi realizatsiei bulevykh funktsii skhemami”, Problemy kibernetiki, 26, Nauka, M., 1973, 207–256

[134] L. A. Sholomov, “A sequence of complexly computable functions”, Math. Notes, 17:6 (1975), 574–579 | DOI | MR | Zbl | Zbl

[135] S. S. Marchenkov, “The complexity of computing exponents”, Math. Notes, 31:3 (1982), 234–237 | DOI | MR | Zbl

[136] A. A. Razborov, “Lower bounds on monotone complexity of the logical permanent”, Math. Notes, 37:6 (1985), 485–493 | DOI | MR | Zbl

[137] A. E. Andreev, “A method for obtaining efficient lower bounds for monotone complexity”, Algebra Logic, 26:1 (1987), 1–18 | Zbl | Zbl

[138] J. E. Hopcroft, R. M. Karp, “An $n^{5/2}$ algorithm for maximun matchings in bipartite graphs”, SIAM J. Comput., 2:4 (1973), 225–231 | DOI | MR | Zbl

[139] L. Lovász, “The works of A. A. Razborov”, Proceedings of the International Congress of Mathematicians (Kyoto, 1990), v. I, Math. Soc. Japan, Tokyo, 1991, 37–40 ; L. Lovas, “O rabotakh A. A. Razborova”, Mezhdunarodnyi kongress matematikov (Kioto, 1990), Mir, M., 1996, 52–58 | MR | Zbl

[140] A. A. Razborov, “Lower bounds for monotone complexity of Boolean functions”, Amer. Math. Soc. Trans. (2), 147 (1990), 75–84 | MR | Zbl

[141] N. Alon, R. B. Boppana, “The monotone circuit complexity of Boolean functions”, Combinatorica, 7:1 (1987), 1–22 | DOI | MR | Zbl

[142] A. Karatsuba, Yu. Ofman, “Umnozhenie mnogoznachnykh chisel”, Dokl. AN SSSR, 145:2 (1962), 293–294

[143] A. L. Toom, “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, Dokl. AN SSSR, 150:3 (1963), 496–498 | MR | Zbl

[144] A. Schönhage, V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing, 7:3-4 (1971), 281–292 ; A. Shenkhage, V. Shtrassen, “Bystroe umnozhenie bolshikh chisel”, Kibernet. sb. Nov. ser., 10, Mir, M., 1973, 87–98 | DOI | MR

[145] A. L. Toom, “O slozhnosti realizatsii dvoichnykh funktsii, imeyuschikh malo podfunktsii”, Problemy kibernetiki, 18, Nauka, M., 1967, 83–90 | MR

[146] D. Ulig, “O svyazi mezhdu slozhnostyu skhemnoi realizatsii funktsii algebry logiki i chislom ikh podfunktsii”, Problemy kibernetiki, 26, Nauka, M., 1973, 183–201 | MR

[147] D. Ulig, “Ob odnom semeistve klassov prosto realizuemykh funktsii algebry logiki”, Problemy kibernetiki, 28, Nauka, M., 1974, 25–42 | MR

[148] V. M. Khrapchenko, “Ob asimptoticheskoi otsenke vremeni slozheniya parallelnogo summatora”, Problemy kibernetiki, 19, Nauka, M., 1967, 101–122

[149] E. Yu. Zakharova, “Ob odnom obobschenii elektronno-lampovykh skhem”, Problemy kibernetiki, 7, Fizmatlit, M., 1962, 43–59

[150] B. A. Subbotovskaya, “Comparison of bases in the realization by formulas of functions of the algebra of logic”, Soviet Math. Dokl., 4 (1963), 478–481 | Zbl

[151] B. A. Muchnik, “One criterion for comparability of bases for the realization of Boolean functions by formulas”, Math. Notes, 1:5 (1967), 341–346 | DOI | MR | Zbl

[152] D. Yu. Cherukhin, “Ob odnoi beskonechnoi posledovatelnosti uluchshayuschikhsya bulevykh bazisov”, Diskret. analiz i issled. oper. Cer. 1, 4:4 (1997), 79–95 | MR | Zbl

[153] D. Yu. Cherukhin, “On the complexity of realization of the linear function by formulas over finite Boolean bases”, Discrete Math. Appl., 10:2 (2000), 147–157 | MR | Zbl

[154] D. Yu. Cherukhin, “Realization of linear functions by formulas in various bases”, Moscow Univ. Math. Bull., 56:6 (2001), 14–18 | MR | Zbl

[155] R. E. Krichevskii, “O realizatsii funktsii superpozitsiyami”, Problemy kibernetiki, 2, Fizmatgiz, M., 1959, 123–138

[156] A. E. Andreev, “On a formula synthesizing method”, Moscow Univ. Math. Bull., 49:6 (1994), 22–25 | Zbl

[157] N. A. Karpova, “O vozmozhnom asimptoticheskom povedenii funktsii Shennona pri realizatsii funktsii algebry logiki formulami”, Problemy kibernetiki, 26, Nauka, M., 1973, 37–51 | MR

[158] E. I. Nechiporuk, “O sinteze logicheskikh setei v nepolnykh i vyrozhdennykh bazisakh”, Problemy kibernetiki, 14, Nauka, M., 1965, 111–160

[159] V. M. Khrapchenko, “O sootnoshenii mezhdu slozhnostyu i glubinoi formul”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, Metody diskretnogo analiza, 32, In-t matematiki SO AN SSSR, Novosibirsk, 1978, 76–94 | MR

[160] S. A. Lozhkin, “Synthesis of formulas whose depth and complexity do not exceed asymptotically the best estimates of high accuracy”, Moscow Univ. Math. Bull., 62:3 (2007), 101–107 | Zbl

[161] O. B. Lupanov, “O vliyanii glubiny formul na ikh slozhnost”, Kibernetika, 1970, no. 2, 46–49 | MR | Zbl

[162] M. J. Fischer, A. R. Meyer, M. S. Paterson, “Lower bounds on the size of Boolean formulas: preliminary report”, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, NM, 1975), Assoc. Comput. Mach., New York, 1975, 37–44 | MR | Zbl

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

[164] B. A. Muchnik (Subbotovskaya), “Otsenka slozhnosti realizatsii lineinoi funktsii formulami v nekotorykh bazisakh”, Kibernetika, 1970, no. 4, 29–38 | Zbl

[165] V. M. Khrapchenko, “Method of determining lower bounds for the complexity of P-schemes”, Math. Notes, 10:1 (1971), 474–479 | DOI | MR | Zbl