Geodesic
Shortest and minimal disjunctive normal forms of complete functions
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 7, pp. 1266-1280 
Yu. V. Maximov. Shortest and minimal disjunctive normal forms of complete functions. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 7, pp. 1266-1280. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_7_a13/
@article{ZVMMF_2015_55_7_a13,
     author = {Yu. V. Maximov},
     title = {Shortest and minimal disjunctive normal forms of complete functions},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1266--1280},
     year = {2015},
     volume = {55},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_7_a13/}
}
TY  - JOUR
AU  - Yu. V. Maximov
TI  - Shortest and minimal disjunctive normal forms of complete functions
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 1266
EP  - 1280
VL  - 55
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_7_a13/
LA  - ru
ID  - ZVMMF_2015_55_7_a13
ER  - 
%0 Journal Article
%A Yu. V. Maximov
%T Shortest and minimal disjunctive normal forms of complete functions
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 1266-1280
%V 55
%N 7
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_7_a13/
%G ru
%F ZVMMF_2015_55_7_a13

Voir la notice de l'article provenant de la source Math-Net.Ru

It was previously established that almost every Boolean function of $n$ variables with $k$ zeros, where $k$ is at most $\log_2n-\log_2\log_2n+1$, can be associated with a Boolean function of $2^{k-1}-1$ variables with $k$ zeros (complete function) such that the complexity of implementing the original function in the class of disjunctive normal forms is determined only by the complexity of implementing the complete function. An asymptotically tight bound is obtained for the minimum possible number of literals contained in the disjunctive normal forms of the complete function.

[1] Zhuravlev Yu. I., Kogan A. Yu., “Realizatsiya bulevykh funktsii s malym chislom nulei diz'yunktivnymi normalnymi formamm i smezhnye zadachi”, Dokl. AN SSSR, 285:4 (1985), 795–799 | MR | Zbl

[2] Zhuravlev Yu. I., Kogan A. Yu., “Algoritm postroeniya diz'yunktivnoi normalnoi formy, ekvivalentnoi proizvedeniyu levykh chastei bulevykh uravnenii nelsonovskogo tipa”, Zh. vychisl. matem. i matem. fiz., 26:8 (1986), 1243–1249 | MR

[3] Kudryavtsev V. B., Andreev A. E., “O slozhnosti algoritmov”, Fundamentalnaya i prikl. matem., 15:3 (2009), 135–181

[4] Zhuravlev Yu. I., “Ob algebraicheskom podkhode k resheniyu zadach raspoznavaniya ili klassifikatsii”, Problemy kibernetiki, 33 (1978), 5–68 | Zbl

[5] Veber K., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Probl. kibernetiki, 36 (1979), 129–158 | Zbl

[6] Zhuravlev Yu. I., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Sibirskii matem. zhurnal, 1:4 (1960), 609–610

[7] Maksimov Yu. V., “Prostye diz'yunktivnye normalnye formy bulevykh funktsii s ogranichennym chislom nulei”, Dokl. AN, 445:2 (2012), 143–145 | Zbl

[8] Maksimov Yu. V., “Realizatsiya bulevykh funktsii s ogranichennym chislom nulei v klasse diz'yunktivnykh normalnykh form”, Zh. vychisl. matem. i matem. fiz., 53:9 (2013), 1569–1588 | Zbl

[9] Dyakonov A. G., “Realizatsiya odnogo klassa bulevykh funktsii s malym chislom nulei tupikovymi diz'yunktivnymi normalnymi formami”, Zh. vychisl. matem. i matem. fiz., 41:5 (2001), 828–835

[10] Dyakonov A. G., “Testovyi podkhod k realizatsii diz'yunktivnymi normalnymi formami bulevykh funktsii s malym chislom nulei”, Zh. vychisl. matem. i matem. fiz., 42:6 (2002), 924–928 | MR | Zbl

[11] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Ucheb. posobie dlya vuzov, 6-e izd., Vyssh. shkola, M., 2010

[12] Mubayi D., Turan G., Zhao Y., “The DNF exception problem”, Theoretical Comput. Sci., 352:1–3 (2006), 85–96 | MR | Zbl

[13] Maksimov Yu. V., “Sravnitelnyi analiz slozhnosti bulevykh funktsii s malym chislom nulei”, Dokl. AN, 447:6 (2012), 607–609 | Zbl

[14] Zhuravlev Yu. I., “Ob otdelimosti podmnozhestv vershin $n$-mernogo edinichnogo kuba”, Tr. MIAN SSSR, 51, 1958, 143–157 | MR | Zbl