RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2014, Volume 21, Number 5, Pages 76–94 (Mi da795)

Minimal complexes of faces of a random Boolean function

I. P. Chukhrov

Institute for Computer Aided Design, RAS, 19/18 2nd Brestskaia St., 123056 Moscow, Russia

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^{n-1}(1+o(1))}$, 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 $n$-dimensional unit cube, random boolean function, complexity measure, minimal complex of faces.

Full text: PDF file (310 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.714.7

Citation: I. P. Chukhrov, “Minimal complexes of faces of a random Boolean function”, Diskretn. Anal. Issled. Oper., 21:5 (2014), 76–94

Citation in format AMSBIB
\Bibitem{Chu14} \by I.~P.~Chukhrov \paper Minimal complexes of faces of a~random Boolean function \jour Diskretn. Anal. Issled. Oper. \yr 2014 \vol 21 \issue 5 \pages 76--94 \mathnet{http://mi.mathnet.ru/da795} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3328839}