Volume 21, No 5, 2014, P. 7694
UDC 519.714.7
I. P. Chukhrov
Minimal complexes of faces of a random Boolean function
Abstract:
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^{n1}\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.
Keywords: face, complex of faces in ndimensional unit cube, random Boolean function, complexity measure, minimal complex of faces.
Chukhrov Igor Petrovich ^{1}
1. Institute for Computer Aided Design, RAS,
19/18 2nd Brestskaia St., 123056 Moscow, Russia
email: chip@icad.org.ru
