Geodesic
Minimal complexes of faces of a~random Boolean function
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 76-94.

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

For almost all Boolean functions in $n$ variables, it is shown that the number of minimal with respect to complexity measure complexes of faces does not exceed $2^{2^{n-1}\left (1+o\left(1\right)\right)}$, if the maximum length of the minimal and length of the shortest complexes of faces are asymptotically equal. For additive complexity measures, we provide effective verifiable sufficient conditions under which the maximum length of the minimal and the length of the shortest complexes of faces are asymptotically equal for almost all Boolean functions. Bibliogr. 17.
Mots-clés : face
Keywords: complex of faces in $n$-dimensional unit cube, random boolean function, complexity measure, minimal complex of faces. 
@article{DA_2014_21_5_a6,
     author = {I. P. Chukhrov},
     title = {Minimal complexes of faces of a~random {Boolean} function},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {76--94},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_5_a6/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - Minimal complexes of faces of a~random Boolean function
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 76
EP  - 94
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_5_a6/
LA  - ru
ID  - DA_2014_21_5_a6
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T Minimal complexes of faces of a~random Boolean function
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 76-94
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_5_a6/
%G ru
%F DA_2014_21_5_a6
I. P. Chukhrov. Minimal complexes of faces of a~random Boolean function. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 5, pp. 76-94. http://geodesic.mathdoc.fr/item/DA_2014_21_5_a6/

[1] Andreev A. E., “Ob odnoi modifikatsii gradientnogo algoritma”, Vestn. MGU. Matematika. Mekhanika, 1985, no. 3, 29–35 | MR | Zbl

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

[3] Glagolev V. V., “Nekotorye otsenki DNF bulevykh funktsii algebry logiki”, Probl. kibernetiki, 19, 1967, 75–94 | MR | Zbl

[4] Zhuravlëv Yu. I., “Otsenka dlya chisla tupikovykh d.n.f. funktsii algebry logiki”, Sib. mat. zhurn., 3:5 (1962), 802–804 | Zbl

[5] Zhuravlëv Yu. I., “Algoritmy postroeniya minimalnykh DNF”, Diskretnaya matematika i matematicheskie voprosy kibernetiki, v. 1, Nauka, M., 1974, 67–98

[6] Korshunov A. D., “Sravnenie slozhnosti dlinneishikh i kratchaishikh DNF i nizhnyaya otsenka chisla tupikovykh DNF dlya pochti vsekh bulevykh funktsii”, Kibernetika, 1969, no. 4, 1–11 | Zbl

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

[8] Kuznetsov S. E., “O nizhnei otsenke dliny kratchaishei DNF pochti vsekh bulevykh funktsii”, Veroyatnostnye metody i kibernetika, 19, Izd-vo Kazan. un-ta, Kazan, 1983, 44–47 | MR

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

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

[11] Sapozhenko A. A., Vvedenie v diskretnuyu matematiku, Izd-vo MGU, M., 1975, 90 pp.

[12] Sapozhenko A. A., Chukhrov I. P., “Minimizatsiya bulevykh funktsii v klasse diz'yunktivnykh normalnykh form”, Itogi nauki i tekhniki. Ser. Teoriya veroyatnosti. Mat. statistika. Teor. kibernetika, 25, 1987, 68–116 | MR | Zbl

[13] Chukhrov I. P., “O yadrovykh i kratchaishikh kompleksakh granei v edinichnom kube”, Diskret. analiz i issled. operatsii, 18:2 (2011), 75–94 | MR | Zbl

[14] Chukhrov I. P., “O minimalnykh kompleksakh granei v edinichnom kube”, Diskret. analiz i issled. operatsii, 19:3 (2012), 79–99 | MR | Zbl

[15] Chukhrov I. P., “O merakh slozhnosti kompleksov granei v edinichnom kube”, Diskret. analiz i issled. operatsii, 20:6 (2013), 77–94 | MR

[16] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Vyssh. shk., M., 2003, 384 pp. | MR

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