Geodesic
On the complexity of minimizing quasicyclic Boolean functions
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 126-151.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the Boolean functions that combine various properties: the extremal values of complexity characteristics of minimization, the inapplicability of local methods for reducing the complexity of the exhaustion, and the impossibility to efficiently use sufficient minimality conditions. Some quasicyclic functions are constructed that possess the properties of cyclic and zone functions, the dominance of vertex sets, and the validity of sufficient minimality conditions based on independent families of sets. For such functions, we obtain the exponential lower bounds for the extent and special sets and also a twice exponential lower bound for the number of shortest and minimal complexes of faces with distinct sets of proper vertices. Bibliogr. 13.
Keywords: minimization of Boolean functions, complexity, extent, independent family of sets.
Mots-clés : domination 
@article{DA_2018_25_3_a4,
     author = {I. P. Chukhrov},
     title = {On the complexity of minimizing quasicyclic {Boolean} functions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {126--151},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_3_a4/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - On the complexity of minimizing quasicyclic Boolean functions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 126
EP  - 151
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_3_a4/
LA  - ru
ID  - DA_2018_25_3_a4
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T On the complexity of minimizing quasicyclic Boolean functions
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 126-151
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_3_a4/
%G ru
%F DA_2018_25_3_a4
I. P. Chukhrov. On the complexity of minimizing quasicyclic Boolean functions. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 126-151. http://geodesic.mathdoc.fr/item/DA_2018_25_3_a4/

[1] Yu. L. Vasil'ev, V. V. Glagolev, “Metric properties of disjunctive normal forms”, Discrete Mathematics and Mathematical Problems of Cybernetics, v. 1, Nauka, Moscow, 1974, 99–148

[2] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[3] A. A. Evdokimov, “Maximal length of circuit in a unitary $n$-dimensional cube”, Math. Notes Acad. Sci. USSR, 6:3 (1969), 642–648 | MR | Zbl

[4] Yu. I. Zhuravlyov, “Algorithms for constructing minimal disjunctive normal forms of Boolean functions”, Discrete Mathematics and Mathematical Problems of Cybernetics, v. 1, Nauka, Moscow, 1974, 67–98

[5] V. B. Kudryavtsev, A. E. Andreev, “On algorithm complexity”, J. Math. Sci., 168:1 (2010), 89–122 | DOI | MR | Zbl

[6] Yu. V. Maksimov, “Realization of Boolean functions with a bounded number of zeros in the class of disjunctive normal forms”, Comput. Math. Math. Phys., 53:9 (2013), 1391–1409 | DOI | DOI | MR

[7] A. V. Panov, “Algorithms using first-order neighborhoods for minimization of Boolean functions”, Comput. Math. Math. Phys., 53:9 (2013), 1410–1420 | DOI | DOI | MR | Zbl

[8] A. A. Sapozhenko, I. P. Chukhrov, “Boolean function minimization in the class of disjunctive normal forms”, J. Sov. Math., 46:4 (1989), 2021–2052 | DOI | MR | Zbl | Zbl

[9] I. P. Chukhrov, “Estimates of the number of minimal disjunctive normal forms for the belt function”, Methods of Discrete Analysis in Functional Systems Research, 36, Inst. Mat. SO AN SSSR, Novosibirsk, 1981, 74–92 | MR

[10] I. P. Chukhrov, “On complexity measures of complexes of faces in the unit cube”, J. Appl. Ind. Math., 8:1 (2014), 9–19 | DOI | MR | Zbl

[11] I. P. Chukhrov, “Proof of covering minimality by generalizing the notion of independence”, J. Appl. Ind. Math., 11:2 (2017), 193–203 | DOI | MR | Zbl

[12] Coudert O., Sasao T., “Two-level logic minimization”, Logic synthesis and verification, Springer Int. Ser. Eng. Comput. Sci., 654, Kluwer Acad. Publ., Norwell, MA, 2001, 1–27

[13] Umans C., Villa T., Sangiovanni-Vincentelli A. L., “Complexity of two-level logic minimization”, IEEE Trans. CAD Integrated Circuits Systems, 25:7 (2006), 1230–1246 | DOI