Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:3, 426-441
Volume 25, No 3, 2018, P. 126-151
UDC 519.714.7
I. P. Chukhrov
On the complexity of minimizing quasicyclic Boolean functions
Abstract:
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, domination, independent family of sets.
DOI: 10.17377/daio.2018.25.601
Igor P. Chukhrov 1
1. Institute of Computer Aided Design RAS,
19/18 Vtoraya Brestskaya St., 123056 Moscow, Russia
e-mail: chip@icad.org.ru
Received 24 November 2017
Revised 19 January 2018
References
[1] Yu. L. Vasil’ev and V. V. Glagolev, Metric properties of disjunctive normal forms, in Diskretnaya matematika i matematicheskie voprosy kibernetiki (Discrete Mathematics and Mathematical Problems of Cybernetics), Vol. 1, pp. 99–148, Nauka, Moscow, 1974.[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.
[3] A. A. Evdokimov, Maximal length of circuit in a unitary $n$-dimensional cube, Mat. Zametki, 6, No. 3, 309–319, 1969. Translated in Math. Notes Acad. Sci. USSR, 6, No. 3, 642–648, 1969.
[4] Yu. I. Zhuravlyov, Algorithms for constructing minimal disjunctive normal forms of Boolean functions, in Diskretnaya matematika i matematicheskie voprosy kibernetiki (Discrete Mathematics and Mathematical Problems of Cybernetics), Vol. 1, pp. 67–98, Nauka, Moscow, 1974.
[5] V. B. Kudryavtsev and A. E. Andreev, On algorithm complexity, Fundam. Prikl. Mat., 15, No. 3, 135–169, 2009. Translated in J. Math. Sci., 168, No. 1, 89–122, 2010.
[6] Yu. V. Maksimov, Realization of Boolean functions with a bounded number of zeros in the class of disjunctive normal forms, Zh. Vychisl. Mat. Mat. Fiz., 53, No. 9, 1569–1588, 2013. Translated in Comput. Math. Math. Phys., 53, No. 9, 1391–1409, 2013.
[7] A. V. Panov, Algorithms using first-order neighborhoods for minimization of Boolean functions, Zh. Vychisl. Mat. Mat. Fiz., 53, No. 9, 1589–1600, 2013. Translated in Comput. Math. Math. Phys., 53, No. 9, 1410–1420, 2013.
[8] A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern., 25, 68–116, 1987. Translated in J. Sov. Math., 46, No. 4, 2021–2052, 1989.
[9] I. P. Chukhrov, Estimates of the number of minimal disjunctive normal forms for the belt function, in Metody diskretnogo analiza v issledovanii funktsional’nykh sistem (Methods of Discrete Analysis in Functional Systems Research), Vol. 36, pp. 74–92, Inst. Mat. SO AN SSSR, Novosibirsk, 1981.
[10] I. P. Chukhrov, On complexity measures of complexes of faces in the unit cube, Diskretn. Anal. Issled. Oper., 20, No. 6, 77–94, 2013. Translated in J. Appl. Ind. Math., 8, No. 1, 9–19, 2014.
[11] I. P. Chukhrov, Proof of covering minimality by generalizing the notion of independence, Diskretn. Anal. Issled. Oper., 24, No. 2, 87–106, 2017. Translated in J. Appl. Ind. Math., 11, No. 2, 193–203, 2017.
[12] O. Coudert and T. Sasao, Two-level logic minimization, in Logic Synthesis and Verification, pp. 1–27, Kluwer Acad. Publ., Netherlands, 2002 (Springer Int. Ser. Eng. Comput. Sci., Vol. 654).
[13] C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli, Complexity of two-level logic minimization, IEEE Trans. CAD Integr. Circuits Syst., 25, No. 7, 1230–1246, 2006.
