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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2012},
     volume = {52},
     number = {10},
     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
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
%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/

[1] Jonson D. S., Yannakakis M., Papadimitriou C. H., “On general all maximal independent sets”, Inform. Proc. Letters, 27 (1988), 119–123 | DOI | MR

[2] Dyukova E. V., Kolesnichenko A. S., “Postroenie i issledovanie polinomialnykh algoritmov dlya zadach logicheskogo analiza dannykh v raspoznavanii”, Matem. metody raspoznavaniya obrazov, Dokl. Mezhdunar. konf. MMRO-15 (Petrozavodsk, 17–23 sentyabrya 2011 g.), 287–290

[3] Gurvich V., Khachiyan L., “On generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions”, Discrete Appl. Math., 96–97:1–3 (1999), 363–373 | DOI | MR | Zbl

[4] Boros E., Elbassioni K., Gurvich V., Khachiyan L., “An efficient implementation of a quasi-Polynomial algorithm for generating hypergraph transversals and its application in joint generation”, Discrete Appl. Math., 154:16 (2006), 2350–2372 | DOI | MR | Zbl

[5] Dyukova E. V., “Ob asimptoticheski optimalnom algoritme postroeniya tupikovykh testov”, Dokl. AN SSSR, 233:4 (1977), 527–530 | MR | Zbl

[6] Dyukova E. V., “Asimptoticheski optimalnye testovye algoritmy v zadachakh raspoznavaniya”, Probl. kibernetiki, 39, Nauka, M., 1982, 165–169 | MR

[7] Dyukova E. V., “O slozhnosti realizatsii nekotorykh protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 45:5 (1987), 938–943 | MR

[8] Dyukova E. V., “Algoritmy raspoznavaniya tipa “Kora”: slozhnost realizatsii i metricheskie svoistva”, Raspoznavanie, klassifikatsiya, prognoz. Matem. metody i ikh primenenie, 2, Nauka, M., 1989, 99–125 | MR

[9] Dyukova E. V., Zhuravlëv Yu. I., “Diskretnyi analiz priznakovykh opisanii v zadachakh raspoznavaniya bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 40:8 (2000), 1264–1278 | MR | Zbl

[10] Dyukova E. V., “O slozhnosti realizatsii diskretnykh (logicheskikh) protsedur raspoznavaniya”, Zh. vychisl. matem. i matem. fiz., 44:3 (2004), 550–572 | MR

[11] Dyukova E. V., “O postroenii tupikovykh pokrytii bulevoi matritsy”, Dokl. RAN, 412:1 (2007), 15–17 | MR

[12] Dyukova E. V., Inyakin A. S., “Asimptoticheski optimalnoe postroenie tupikovykh pokrytii tselochislennoi matritsy”, Matem. voprosy kibernetiki, 17, Nauka, M., 2008, 235–246

[13] Djukova E. V., Nefedov V. Yu., “The Complexity of transformation of normal forms for characteristic functions of classes”, Pat. Recogn. Image Analys., 19:3 (2009), 435–440 | DOI

[14] Noskov V. N., Slepyan V. A., “O chisle tupikovykh testov dlya odnogo klassa tablits”, Kibernetika. Kiev, 1972, no. 1, 60–65 | MR | Zbl

[15] Sapozhenko A. A., “Otsenka chisla tupikovykh d.n.f. dlya pochti vsekh ne vsyudu opredelennykh bulevykh funktsii”, Matem. zametki, 28:2 (1980), 279–299 | MR

[16] Andreev A. E., “Ob asimptoticheskom povedenii chisla tupikovykh testov i dliny minimalnogo testa dlya pochti vsekh tablits”, Probl. kibernetiki, 41, Nauka, M., 1984, 117–142 | MR

[17] Dyukova E. V., “O chisle tupikovykh pokrytii tselochislennoi matritsy”, Zh. vychisl. matem. i matem. fiz., 45:5 (2005), 938–943 | MR

[18] Demyanov E. A., Dyukova E. V., “O postroenii tupikovykh pokrytii tselochislennoi matritsy”, Zh. vychisl. matem. i matem. fiz., 47:3 (2007), 539–547 | MR

[19] Dyukova E. V., Sotnezov R. M., “O slozhnosti diskretnykh zadach perechisleniya”, Dokl. RAN, 435:1 (2010), 11–13 | MR

[20] Dyukova E. V., Sotnezov R. M., “Asimptoticheskie otsenki chisla reshenii zadachi dualizatsii i ee obobschenii”, Zh. vychisl. matem. i matem. fiz., 51:8 (2011), 1431–1440 | MR | Zbl