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/