On minimal complexes of faces in the unit cube

I. P. Chukhrov

Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 3, pp. 79-99

Résumé

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.

Détail

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.