This article is cited in 1 paper

On the complexity of minimizing quasicyclic Boolean functions

I. P. Chukhrov

Institute of Computer Aided Design RAS, 19/18 Vtoraya Brestskaya St., 123056 Moscow, Russia

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.

UDC: 519.714.7

Received: 24.11.2017
Revised: 19.01.2018

DOI: 10.17377/daio.2018.25.601

 English version: Journal of Applied and Industrial Mathematics, 2018, 12:3, 426–441

Bibliographic databases:

• 
•