Geodesic
On minimal complexes of faces in the unit cube
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 79-99.

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

We consider the problem of construction of minimal complexes of faces in the unit $n$-dimensional cube for the class of complexity measures such that the complexity of a complex does not change upon replacement of some faces with faces isomorphic with respect to permutation of coordinates. This class contains all known complexity measures used in the minimization of Boolean functions in the class of DNF. It is shown that the number of complexes of faces of dimension at most $k$ which are minimal for all complexity measures of this class has the same order as the logarithm of the number of complexes of no more than $2^{n-1}$ different faces of dimension at most $k$ for $1\le k\le c\cdot n$ and $c0.5$. The number of functions with “large” number of minimal complexes has the same order as the logarithm of the number of all functions. Similar estimates are valid for the maximum number of DNF Boolean functions which are minimal for all complexity measures of this class. These results show that the problem of complexity in the minimization of Boolean functions are determined by the structural properties of the set of vertices of a Boolean function in the unit cube, i.e. the properties of domain in which the functional is minimized rather than the properties of the complexity measure functional. Ill. 1, bibliogr. 9.
Mots-clés : face, interval
Keywords: complex of faces in $n$-dimensional unit cube, Boolean function, complexity measure, minimal covering, number of minimal complexes of faces. 
@article{DA_2012_19_3_a6,
     author = {I. P. Chukhrov},
     title = {On minimal complexes of faces in the unit cube},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {79--99},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_3_a6/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On minimal complexes of faces in the unit cube
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 79
EP  - 99
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_3_a6/
LA  - ru
ID  - DA_2012_19_3_a6
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On minimal complexes of faces in the unit cube
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 79-99
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_3_a6/
%G ru
%F DA_2012_19_3_a6
I. P. Chukhrov. On minimal complexes of faces in the unit cube. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 79-99. http://geodesic.mathdoc.fr/item/DA_2012_19_3_a6/

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

[2] Veber K., “O razlichnykh ponyatiyakh minimalnosti diz'yunktivnykh normalnykh form”, Problemy kibernetiki, 36, 1979, 129–158 | MR | Zbl

[3] Zhuravlev Yu. I., “O razlichnykh ponyatiyakh minimalnosti d.n.f.”, Sib. mat. zhurn., 1:4 (1960), 609–611

[4] Zhuravlev Yu. I., “Algoritmy postroeniya minimalnykh d.n.f.”, Diskret. matematika i mat. voprosy kibernetiki, v. 1, Nauka, M., 1974, 67–98

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

[6] 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

[7] Chukhrov I. P., “O chisle minimalnykh diz'yunktivnykh normalnykh form”, Dokl. AN SSSR, 276:6 (1984), 1335–1339 | MR | Zbl

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

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