×

On the complexity of the dualization problem. (Russian, English) Zbl 1274.68137

Zh. Vychisl. Mat. Mat. Fiz. 52, No. 10, 1926-1935 (2012); translation in Comput. Math. Math. Phys. 52, No. 10, 1472-1481 (2012).
Summary: 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 polynomial-time-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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms
15B34 Boolean and Hadamard matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. S. Jonson, M. Yannakakis, and C. H. Papadimitriou, “On General All Maximal Independent Sets,” Inf. Proc. Lett. 27, 119-123 (1988). · Zbl 0654.68086 · doi:10.1016/0020-0190(88)90065-8
[2] E. V. Djukova and A. S. Kolesnichenko, “Design and Investigation of Polynomial-Time Algorithms for Logical Analysis of Data in Pattern Recognition, <Emphasis Type=”Italic”>Proceedings of International Conference on Mathematical Methods in Pattern Recognition (MMPR-15), Petrozavodsk, September 17-23, 2011 (Petrozavodsk, 2011), pp. 287-290.
[3] V. Gurvich and L. Khachiyan, “On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions,” Discrete Appl. Math. 96-97(1-3), 363-373 (1999). · Zbl 0953.06013 · doi:10.1016/S0166-218X(99)00099-2
[4] E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan, “An Efficient Implementation of a Quasi-Polynomial Algorithm for Generating Hypergraph Transversals and Its Application in Joint Generation,” Discrete Appl. Math. 154, 2350-2372 (2006). · Zbl 1110.68104 · doi:10.1016/j.dam.2006.04.012
[5] E. V. Djukova, “Asymptotically Optimal Algorithm for Constricting Irredundant Tests,” Dokl. Akad. Nauk SSSR 233, 527-530 (1977).
[6] Djukova, E. V., Asymptotically Optimal Test Algorithms in Recognition Problems, 165-169 (1982), Moscow
[7] E. V. Dyukova, “The Complexity of the Realization of Certain Recognition Procedures,” USSR Comput. Math. Math. Phys. 27(1), 74-83 (1987). · Zbl 0648.68091 · doi:10.1016/0041-5553(87)90121-2
[8] Djukova, E. V., Recognition Algorithms of the Kora Type: Complexity of Implementation and Metric Properties, 99-125 (1989), Moscow
[9] E. V. Djukova and Yu. I. Zhuravlev, “Discrete Analysis of Feature Descriptions in Recognition Problems of High Dimensionality,” Comput. Math. Math. Phys. 40, 1214-1227 (2000). · Zbl 0996.68162
[10] E. V. Djukova, “On the Implementation Complexity of Discrete (Logical) Recognition Procedures,” Comput. Math. Math. Phys. 44, 532-541 (2004).
[11] E. V. Djukova, “Construction of Irredundant Coverings of a Boolean Matrix,” Dokl. Math. 75, 9-11 (2007). · Zbl 1327.68343 · doi:10.1134/S1064562407010036
[12] Djukova, E. V.; Inyakin, A. S., Asymptotically Optimal Constriction of Irredundant Coverings of an Integer Matrix, 235-246 (2008), Moscow
[13] E. V. Djukova and V. Yu. Nefedov, “The Complexity of Transformation of Normal Forms for Characteristic Functions of Classes,” Pattern Recogn. Image Anal. 19, 435-440 (2009). · doi:10.1134/S1054661809030079
[14] V. N. Noskov and V. A. Slepyan, “On the Number of Irredundant Tests for a Class of Tables,” Kibernetika, No. 1, 60-65 (1972).
[15] A. A. Sapozhenko, “Estimation of the Length and the Number of Dead-End Disjunctive Normal Forms for Almost All Partial Boolean Functions,” Math. Notes 28, 603-615 (1980). · Zbl 0452.94034 · doi:10.1007/BF01157923
[16] Andreev, A. E., On the Asymptotic Behavior of the Number of Irredundant Tests and the Length of a Minimal Test for Almost All Tables, 117-142 (1984), Moscow · Zbl 0566.68071
[17] E. V. Djukova, “On the Number of Irreducible Coverings of an Integer Matrix,” Comput. Math. Math. Phys. 45, 903-908 (2005).
[18] E. A. Dem’yanov and E. V. Djukova, “On the Construction of Irredundant Coverings of an Integer Matrix,” Comput. Math. Math. Phys. 47, 518-526 (2007). · Zbl 1203.68176 · doi:10.1134/S0965542507030141
[19] E. V. Djukova and R. M. Sotnezov, “On the Complexity of Discrete Generation Problems,” Dokl. Math. 82, 847-849 (2010). · Zbl 1215.68110 · doi:10.1134/S1064562410060025
[20] E. V. Djukova and R. M. Sotnezov, “Asymptotic Estimates for the Number of Solutions of the Dualization Problem and Its Generalizations,” Comput. Math. Math. Phys. 51, 1431-1440 (2011). · Zbl 1249.49050 · doi:10.1134/S0965542511080069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.