Geodesic
On the complexity of the dualization problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 10, pp. 1926-1935

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

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form. 
@article{ZVMMF_2012_52_10_a12,
     author = {E. V. Dyukova and R. M. Sotnezov},
     title = {On the complexity of the dualization problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1926--1935},
     publisher = {mathdoc},
     volume = {52},
     number = {10},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_10_a12/}
}
TY  - JOUR
AU  - E. V. Dyukova
AU  - R. M. Sotnezov
TI  - On the complexity of the dualization problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2012
SP  - 1926
EP  - 1935
VL  - 52
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_10_a12/
LA  - ru
ID  - ZVMMF_2012_52_10_a12
ER  - 
%0 Journal Article
%A E. V. Dyukova
%A R. M. Sotnezov
%T On the complexity of the dualization problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2012
%P 1926-1935
%V 52
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_10_a12/
%G ru
%F ZVMMF_2012_52_10_a12
E. V. Dyukova; R. M. Sotnezov. On the complexity of the dualization problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 10, pp. 1926-1935. http://geodesic.mathdoc.fr/item/ZVMMF_2012_52_10_a12/