zbMATH — the first resource for mathematics

Minimization of algorithms for some classes of polynomials of Boolean variables. (Russian) Zbl 0699.90072
Tr. Inst. Mat. 10, 5-17 (1988).
Minimization problems of polynomials of Boolean variables are studied. Some sets of NP-difficult problems are revealed. Minimization algorithms are constructed and studied for a series of special polynomials. In particular an efficient minimization algorithm for submodular functions is provided.
Reviewer: K.R.Ajda-Zade

90C09 Boolean programming
68Q25 Analysis of algorithms and problem complexity