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., 2012, Volume 19, Number 3, Pages 79–99 (Mi da692)

On minimal complexes of faces in the unit cube

I. P. Chukhrov

Institute of Automatization of Designing, RAS, Moscow, Russia

Abstract: 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 $c<0.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.

Keywords: face, interval, complex of faces in $n$-dimensional unit cube, Boolean function, complexity measure, minimal covering, number of minimal complexes of faces.

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

English version:
Journal of Applied and Industrial Mathematics, 2012, 6:1, 42–55

Bibliographic databases:

UDC: 519.95

Citation: I. P. Chukhrov, “On minimal complexes of faces in the unit cube”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 79–99; J. Appl. Industr. Math., 6:1 (2012), 42–55

Citation in format AMSBIB
\Bibitem{Chu12} \by I.~P.~Chukhrov \paper On minimal complexes of faces in the unit cube \jour Diskretn. Anal. Issled. Oper. \yr 2012 \vol 19 \issue 3 \pages 79--99 \mathnet{http://mi.mathnet.ru/da692} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2986643} \zmath{https://zbmath.org/?q=an:06460012} \elib{http://elibrary.ru/item.asp?id=17723717} \transl \jour J. Appl. Industr. Math. \yr 2012 \vol 6 \issue 1 \pages 42--55 \crossref{https://doi.org/10.1134/S1990478912010061} 

• http://mi.mathnet.ru/eng/da692
• http://mi.mathnet.ru/eng/da/v19/i3/p79

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. I. P. Chukhrov, “On complexity measures for complexes of faces in the unit cube”, J. Appl. Industr. Math., 8:1 (2014), 9–19
2. I. P. Chukhrov, “Minimalnye kompleksy granei sluchainoi bulevoi funktsii”, Diskretn. analiz i issled. oper., 21:5 (2014), 76–94
3. I. P. Chukhrov, “On the problem of minimizing a single set of Boolean functions”, J. Appl. Industr. Math., 9:3 (2015), 335–350
•  Number of views: This page: 528 Full text: 49 References: 27 First page: 3