On algorithm complexity

V. B. Kudryavtsev ; A. E. Andreev

Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 135-181.

Résumé

This paper contains review of the authors' results in the theory of algorithm complexity. The results described concern the methods for obtaining lower bounds (containing almost all exponential lower bounds on monotone complexity of monotone functions), asymptotically optimal functional networks' synthesis, Boolean functions minimization, and the problems of solving Boolean equations.

Bibliographie

[1] Andreev A. E., O kachestvennykh i metricheskikh svoistvakh testovykh algoritmov, Avtoref. dis. $\dots$ kand. fiz.-mat. nauk, M., 1981

[2] Andreev A. E., “O tupikovykh i minimalnykh testakh”, DAN SSSR, 256:3 (1981), 521–524 | MR | Zbl

[3] Andreev A. E., “K probleme minimizatsii diz'yunktivnykh normalnykh form”, DAN SSSR, 274:2 (1984), 265–269 | MR | Zbl

[4] Andreev A. E., “O sinteze samokorrektiruyuschikhsya upravlyayuschikh sistem”, DAN SSSR, 277:3 (1984), 521–525 | MR | Zbl

[5] Andreev A. E., “Ob asimptoticheskom povedenii chisla tupikovykh testov i minimalnoi dliny testa dlya pochti vsekh tablits”, Problemy kibernetiki, 41, 1984, 117–141 | MR | Zbl

[6] Andreev A. E., “Metod bespovtornoi reduktsii sinteza samokorrektiruyuschikhsya skhem”, DAN SSSR, 283:2 (1985), 265–269 | MR | Zbl

[7] Andreev A. E., “O sinteze kontaktnykh mnogopolyusnikov”, 7-ya Vsesoyuznaya konferentsiya “Problemy teoreticheskoi kibernetiki”, Tezisy dokladov, Irkutsk, 1985, 9–10

[8] Andreev A. E., O sinteze topologicheskikh funktsionalnykh setei, Preprint No 259, IPMekh AN SSSR i MGU im. M. V. Lomonosova, 1985

[9] Andreev A. E., O sinteze funktsionalnykh setei, Dis. $\dots$ dokt. fiz.-mat. nauk, M., 1985

[10] Andreev A. E., “O slozhnosti monotonnykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1985, no. 4, 83–87 | MR | Zbl

[11] Andreev A. E., Ob odnom metode polucheniya nizhnikh otsenok slozhnosti individualnykh monotonnykh funktsii, Preprint No 248, IPMekh AN SSSR i MGU, 1985

[12] Andreev A. E., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti individualnykh monotonnykh funktsii”, DAN SSSR, 281:2 (1985), 1033–1037

[13] Andreev A. E., “Universalnyi printsip samokorrektirovaniya”, Mat. sb., 127(169):2 (1985), 147–172 | MR | Zbl

[14] Andreev A. E., “Ob odnom metode polucheniya bolee chem kvadratichnykh effektivnykh nizhnikh otsenok slozhnosti $\pi$-skhem”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1987, no. 1, 70–73 | Zbl

[15] Andreev A. E., “Ob odnom metode polucheniya effektivnykh nizhnikh otsenok monotonnoi slozhnosti”, Algebra i logika, 1987, no. 1, 3–26 | Zbl

[16] Bibilo P. N., Enin S. V., “Dekompozitsiya bulevoi funktsii s minimalnym chislom suschestvennykh argumentov podfunktsii”, Izv. AN SSSR. Tekhn. kib., 1980, no. 3, 123–129 | MR | Zbl

[17] Vasilev Yu. L., “O sravnenii slozhnosti tupikovykh i minimalnykh diz'yunktivnykh normalnykh form”, Problemy kibernetiki, 10, 1963, 5–61 | MR

[18] Vasilev Yu. L., “K voprosu o chisle tupikovykh i minimalnykh diz'yunktivnykh normalnykh form”, Diskretnyi analiz, 2, In-t matematiki SO AN SSSR, Novosibirsk, 1964, 3–9 | MR

[19] Vasilev Yu. L., “Massivnye klassy plotnykh bulevykh funktsii”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, 32, In-t matematiki SO AN SSSR, Novosibirsk, 1978, 21–33 | MR

[20] Vikulin A. P., “Otsenka chisla kon'yunktsii v sokraschënnoi d. n. f.”, Problemy kibernetiki, 19, 1974, 151–166 | MR

[21] Glagolev V. V., “Otsenka slozhnosti sokraschënnoi diz'yunktivnoi normalnoi formy dlya pochti vsekh funktsii algebry logiki”, DAN SSSR, 158:4 (1964), 770–773 | MR | Zbl

[22] Gorelik A. L., Skripkin V. A., Metody raspoznavaniya, Vysshaya shkola, M., 1984 | MR

[23] Grigoryan Yu. G., “Algoritm resheniya sistemy logicheskikh uravnenii”, ZhVM i MF, 2:1 (1962), 186–189 | MR

[24] S. V. Yablonskii, O. B. Lupanov (obsch. red.), Diskretnaya matematika i matematicheskie voprosy kibernetiki, T. 1, Nauka, M., 1974 | Zbl

[25] Dyukova E. V., “Ob asimptoticheski optimalnom algoritme postroeniya tupikovykh testov dlya binarnykh tablits”, Problemy kibernetiki, 34, 1978, 169–186 | MR | Zbl

[26] Egiazaryan E. V., “Ob odnom klasse sistem bulevykh uravnenii”, ZhVM i MF, 1976, no. 4, 1073–1077 | Zbl

[27] Egiazaryan E. V., “Otsenki, svyazannye s chislom reshenii sistem bulevykh uravnenii”, Voprosy kibernetiki, kombinatornyi analiz i teoriya grafov, 64, 1980, 124–130 | Zbl

[28] Egiazaryan E. V., “Metricheskie svoistva sistem bulevykh uravnenii”, Dokl. AN Arm. SSR, 72:2 (1981), 67–72 | MR | Zbl

[29] Zhuravlëv Yu. I., “Algoritmy uproscheniya diz'yunktivnykh normalnykh form konechnogo indeksa”, DAN SSSR, 139:6 (1961), 1329–1331 | MR | Zbl

[30] Zhuravlëv Yu. I., “Teoretiko-mnozhestvennye metody algebry logiki”, Problemy kibernetiki, 8, 1962, 5–14

[31] Zhuravlëv Yu. I., “Otsenka slozhnosti lokalnykh algoritmov dlya nekotorykh ekstremalnykh zadach na konechnykh mnozhestvakh”, DAN SSSR, 158:5 (1964), 1018–1021 | Zbl

[32] Zhuravlëv Yu. I., “Lokalnye algoritmy vychisleniya informatsii”, Kibernetika, 1965, no. 1, 12–19 | MR | Zbl

[33] Zakrevskii A. D., Algoritmy sinteza diskretnykh avtomatov, Nauka, M., 1971 | MR | Zbl

[34] Zakrevskii A. D., Logicheskie uravneniya, Nauka i tekhnika, Minsk, 1975 | MR | Zbl

[35] Kabulov A. V., Prilozheniya diskretnoi matematiki k kibernetike, FAN, Tashkent, 1982 | MR

[36] Kabulov A. V., Igamberdyev T. M., “Ob odnom podkhode k resheniyu sistem logicheskikh uravnenii”, Voprosy vychislitelnoi i prikladnoi matematiki, 74, 1984, 68–73 | Zbl

[37] Kirienko G. I., “O samokorrektiruyuschikhsya skhemakh iz funktsionalnykh elementov”, Problemy kibernetiki, 12, 1964, 29–37 | MR

[38] Kirienko G. I., “Sintez samokorrektiruyuschikhsya skhem iz funktsionalnykh elementov dlya sluchaya rastuschego chisla oshibok v skheme”, Diskretnyi analiz, 16, In-t matematiki SO AN SSSR, Novosibirsk, 1970, 38–43 | MR

[39] Kovalenko I. N., “K vychisleniyu veroyatnosti edinstvennosti resheniya sistemy sluchainykh nelineinykh bulevykh uravnenii”, Kibernetika, 1973, no. 3, 12–15 | MR

[40] Konstantinov R. M., Korolëva Z. E., “Primenenie testovykh algoritmov k zadacham geologicheskogo prognozirovaniya”, Raspoznavanie obrazov, Trudy Mezhdunarodnogo simpoziuma 1971 g. po prakticheskim primeneniyam metodov raspoznavaniya obraztsov VTs AN SSSR, M., 1973, 194–204

[41] Korshunov A. D., “O chisle monotonnykh bulevykh funktsii”, Problemy kibernetiki, 38, 1981, 5–108 | MR | Zbl

[42] Korshunov A. D., “O khromaticheskom chisle $n$-vershinnykh grafov”, Metody diskretnogo analiza v teorii bulevykh funktsii, 35, In-t matematiki SO AN SSSR, Novosibirsk, 1980, 15–44 | MR

[43] Kuznetsov S. E., “Nizhnyaya otsenka funktsii Shennona dlya p-skhem bez nulevykh tsepei”, Diskretnyi analiz, 37, In-t matematiki SO AN SSSR, Novosibirsk, 1981, 51–64

[44] Kuzyurin N. N., Kombinatorno-algebraicheskie metody v prikladnoi matematike, Gorkii, 1980, 88–98 | MR | Zbl

[45] Kurosh A. G., Kurs vysshei algebry, Nauka, M., 1975 | MR | Zbl

[46] Leontev V. K., Nurlybaev A. N., “Ob odnom klasse sistem bulevykh uravnenii”, ZhVM i MF, 15:6 (1975), 1568–1579 | MR | Zbl

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

[48] Lupanov O. B., “O sinteze kontaktnykh skhem”, DAN SSSR, 119:1 (1958), 23–26 | MR | Zbl

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

[50] Lupanov O. B., “O slozhnosti realizatsii funktsii algebry logiki formulami”, Problemy kibernetiki, 3, 1960, 61–80 | MR | Zbl

[51] Lupanov O. B., “O printsipe lokalnogo kodirovaniya i realizatsii funktsii iz nekotorykh klassov skhemami iz funktsionalnykh elementov”, DAN SSSR, 140:2 (1961), 322–325 | MR | Zbl

[52] Lupanov O. B., “Ob odnom klasse skhem iz funktsionalnykh elementov (formuly s konechnoi pamyatyu)”, Problemy kibernetiki, 7, 1962, 61–114 | Zbl

[53] Lupanov O. B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, 1963, 63–97 | MR | Zbl

[54] Lupanov O. B., “O slozhnosti realizatsii funktsii algebry logiki releino-kontaktnymi skhemami”, Problemy kibernetiki, 11, 1964, 25–47 | MR | Zbl

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

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

[57] Madatyan Kh. A., “O sinteze skhem korrektiruyuschikh razmykanii kontaktov”, DAN SSSR, 159:2 (1964), 290–293

[58] Markov A. A., “O minimalnykh kontaktno-ventilnykh dvupolyusnikakh dlya monotonnykh simmetricheskikh funktsii”, Problemy kibernetiki, 8, 1962, 117–122 | MR

[59] Matrosova A. Yu., “Ob ob'ëme vychislenii pri reshenii bulevykh uravnenii”, Mat. sb. Tomskogo un-ta, 1975, no. 2, 120–128 | MR

[60] Nguen Kim An, “Nekotorye kharakteristiki algoritmov minimizatsii bulevykh funktsii”, Tezisy dokladov IV Vsesoyuznoi konferentsii po matematicheskoi logike, Tbilisi, 1982

[61] Nguen Kim An, “O nekotorykh kharakteristikakh algoritmov minimizatsii bulevykh funktsii”, DAN SSSR, 267 (1982), 1058–1062 | MR | Zbl

[62] Nechepurenko M. N., “Elementy buleva intervalnogo analiza”, Sistemnoe modelirovanie v informatike, VTs SO AN SSSR, Novosibirsk, 1985, 37–61

[63] Nechiporuk E. I., “Ob odnoi bulevskoi funktsii”, DAN SSSR, 169:4 (1966), 765–767

[64] Nechiporuk E. I., “O korrektirovanii obryvov v ventilnykh i kontaktnykh skhemakh”, Kibernetika, 1968, no. 5, 40–48

[65] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, DAN SSSR, 179:4 (1968), 786–789

[66] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, Problemy kibernetiki, 21, 1969, 5–102 | Zbl

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

[68] Nechiporuk E. I., “O realizatsii diz'yunktsii i kon'yunktsii v nekotorykh monotonnykh bazisakh”, Problemy kibernetiki, 23, 1970, 291–294

[69] Nechiporuk E. I., “O topologicheskikh printsipakh samokorrektirovaniya”, Problemy kibernetiki, 26, 1973, 19–26 | Zbl

[70] Okolnishnikova E. A., “Monotonnaya buleva sistema s kvadratichnoi slozhnostyu realizatsii v bazise $\{\,\vee,0,1\}$”, Diskretnyi analiz, 41, In-t matematiki SO AN SSSR, Novosibirsk, 1984, 81–98 | MR

[71] Ortyukov S. I., “Ob otsenkakh funktsii Shennona dlya skhem iz nenadëzhnykh funktsionalnykh elementov”, Problemy kibernetiki, 40, 1983, 269

[72] Potapov Yu. G., Yablonskii S. V., “O sinteze samokorrektiruyuschikhsya kontaktnykh skhem”, DAN SSSR, 134:3 (1960), 543–547

[73] Razborov A. A., “Nizhnie otsenki monotonnoi slozhnosti logicheskogo permanenta”, Mat. zametki, 37:6 (1985), 887–900 | MR | Zbl

[74] Razborov A. A., “Nizhnie otsenki monotonnoi slozhnosti nekotorykh bulevykh funktsii”, DAN SSSR, 281:4 (1985), 798–801 | MR | Zbl

[75] Redkin N. P., “O samokorrektirovanii kontaktnykh skhem”, Problemy kibernetiki, 33, 1978, 119–138 | MR | Zbl

[76] Redkin N. P., “O samokorrektirovanii kontaktnykh skhem. II”, Problemy kibernetiki, 36, 1979, 195–208 | MR | Zbl

[77] Sapozhenko A. A., “Metricheskie svoistva pochti vsekh funktsii algebry logiki”, Diskretnyi analiz, 10, In-t matematiki SO AN SSSR, Novosibirsk, 1967, 91–119

[78] Sapozhenko A. A., “Poryadok okrestnosti maksimalnykh intervalov u pochti vsekh bulevykh funktsii”, DAN SSSR, 180:1 (1968), 32–35 | MR | Zbl

[79] Safaryan A. A., NP-polnota zadachi razbieniya sistem bulevykh uravnenii na minimalnye bloki, VTs AN SSSR, M., 1984

[80] Safaryan A. A., “O reshenii sistem bulevykh uravnenii, voznikayuschikh pri postroenii testov i sistem nelsonovskogo tipa”, ZhVM i MF, 24:10 (1984), 1590–1593 | MR

[81] Svoboda A., Chulik K., “Algoritm dlya resheniya bulevykh uravnenii”, Avtomatika i telemekhanika, 25:3 (1964), 374–381 | MR | Zbl

[82] Serikov Yu. A., “Algebraicheskii metod resheniya logicheskikh uravnenii”, Izv. AN SSSR. Tekhn. kib., 1972, no. 2, 114–124 | MR | Zbl

[83] Solovëv N. A., Testy, Nauka, Novosibirsk, 1978

[84] Subbotovskaya B. A., “O realizatsii lineinykh funktsii formulami v bazise $\,\vee,\neg$”, DAN SSSR, 136:3 (1961), 553–555 | Zbl

[85] Ulig D., “O sinteze samokorrektiruyuschikhsya skhem iz funktsionalnykh elementov s malym chislom nenadëzhnykh elementov”, Mat. zametki, 15:6 (1974), 937–944 | MR | Zbl

[86] Ulig D., “Samokorrektiruyuschiesya kontaktnye skhemy, ispravlyayuschie bolshoe chislo oshibok”, DAN SSSR, 241:6 (1978), 1273–1276 | MR

[87] Utkin A. A., “Reshenie logicheskikh uravnenii”, Avtomatizatsiya logicheskogo proektirovaniya, ITK AN BSSR, Minsk, 1982, 41–58

[88] Feller V., Vvedenie v teoriyu veroyatnostei i eë prilozheniya, T. 1, Mir, M., 1984 | MR | Zbl

[89] Kholl M., Kombinatorika, Mir, M., 1970 | MR

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

[91] Khrapchenko V. M., “Nizhnie otsenki slozhnosti skhem iz funktsionalnykh elementov (obzor)”, Kibernet. sbornik, 21, 1984, 3–54 | MR | Zbl

[92] Chistov V. P., O sistemakh logicheskikh uravnenii, Dep. v In-t mat. i mekh. Ural. nauch. tsentra AN SSSR, Sverdlovsk, 1984

[93] Sholomov L. A., “O realizatsii nedoopredelënnykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 21, 1969, 215–226 | Zbl

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

[95] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Tr. MIAN SSSR, 51, 1958, 5–142 | MR | Zbl

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

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

[98] Yablonskii S. V., Demidova N. G., Konstantinov R. M., Korolëva Z. E., Kudryavtsev V. B., Sirotskaya S. V., “Testovyi podkhod k otsenke geologo-strukturnykh faktorov i masshtabov orudneniya”, Geologiya rudnykh mestorozhdenii, 13:2 (1971), 30–42

[99] Banković D., “Solving systems of arbitraty equations”, Discrete Math., 46:3 (1983), 305–309 | DOI | MR | Zbl

[100] Bochman D., Posthoff Ch., “Die Behandlung Boolescher Gleichungen mit Hilfe des Booleschen Differentialkalküls”, Probleme und Ergebnisse aus der Arbeitsgruppe Kybernetik, Informationsverarbeitung der Klasse Mathematik 1977/78, Akademie, Berlin, 1981, 5–25 | MR

[101] Brown F. M., “Reduced solutions of Boolean equations”, IEEE Trans. Comput., 19 (1970), 976–981 | DOI | Zbl

[102] Föllinger O., “Boolesche Gleichungen, Lösung und Anwendungen. I. Die Lösung Boolescher Gleichungen”, Elektron. Datenverarb., 1963, 253–260 | Zbl

[103] Katona G., “A theorem of finite sets”, Theory of Graph, New York, 1969, 187–208 | MR

[104] Mehlhorn K., “Some remarks on Boolean sums”, Acta Inform., 12 (1979), 371–375 | DOI | MR | Zbl

[105] Mehlhorn K., Galil Z., “Monotone switching circuits and Boolean matrix product”, Computing, 16 (1976), 99–111 | DOI | MR | Zbl

[106] Paterson M. S., “Complexity of monotone networks for Boolean matrix product”, Theor. Comput. Sci., 1 (1975), 13–20 | DOI | MR | Zbl

[107] Peeva K., “Systems of linear equations over a bounded chain”, Acta Cybernet., 7:2 (1985), 195–202 | MR | Zbl

[108] Pipendger N., On another Boolean matrix, IBM Research Report RC-6914, 1977

[109] Pratt V. P., “The effect of basis on size of Boolean expressions”, Proc. of 16th Ann. Symp. Found. of Comput. Sci., New York, 1975, 119–121 | MR | Zbl

[110] Skala H., “The general solution of an arbitrary Boolean equations”, Amer. Math. Monthly, 74:9 (1967), 1074–1077 | DOI | MR | Zbl

[111] Shannon C. E., “The synthesis of two-terminal swithing circuits”, Bell System Tech. J., 28:1 (1949), 59–98 | DOI | MR

[112] Svoboda A., “An algorithm for solving Boolean equations”, IEEE Trans. Electron. Comput., 1963, no. 12, 557–559 | DOI | MR | Zbl

[113] Tapia M. A., Tucker J. H., “Complete solution of Boolean equations”, IEEE Trans. Comput., 29:7 (1980), 662–665 | DOI | MR | Zbl

[114] Vaquero A., Iglesias M., “Aplicación del método de resolución de S.E.B. de Tapia Tucker a la síntesis de funciones múltiples”, Rev. Inform. Automát., 16 (1983), 35–39

[115] Wegener I., “Switching functions whose monotone complexity in nearly quadratic”, Theor. Comput. Sci., 9 (1979), 83–97 | DOI | MR | Zbl