EN|RU Volume 18, No 2, 2011, P. 75-94 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^{n-1}$ 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 n-dimensional 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 e-mail: chip@icad.org.ru © Sobolev Institute of Mathematics, 2015