Volume 18, No 2, 2011, P. 7594
UDC 519.95
I. P. Chukhrov
On kernel and shortest complexes of faces in the unit cube
Abstract:
Studying extreme kernel complexes of faces of given dimension, we obtain lower estimates of the number of shortest complexes of faces in the unit $n$dimensional cube. It is shown that the number of shortest complex $k$dimensional faces is of the same logarithm order as the number of complexes consisting of no more than $2^{n1}$ different faces of dimension $k$, with $1\le k\le c\cdot n$ and $c<0.5$. This implies similar lower bounds for the maximum length of kernel and the number of shortest DNF Boolean functions.
Bibliogr. 15.
Keywords: face, interval, kernel face, complex of faces in ndimensional unit cube, boolean function, shortest covering.
Chukhrov Igor Petrovich ^{1}
1. Institute of Automatization of Designing, RAS,
19/18 2nd Brestskaia str., 123056 Moscow, Russia
email: chip@icad.org.ru
