×

On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions. (English) Zbl 0953.06013

Suppose a monotone Boolean function \(f\) is given as a black box such that \(f\) for any input vector can be evaluated in polynomial time. The paper addresses the problem of constructing the set \(C\) of prime implicates of \(f\) and the set \(D\) of prime implicants of \(f\). The following result about the incremental complexity of this problem is obtained: For given sets \(C'\subseteq C\), \(D'\subseteq D\), an element of \((C\cup D)\setminus(C'\cup D')\) can be produced in quasipolynomial time. On the other hand, it is proven that if uniform sampling from within \(C\cup D\) can be done in quasipolynomial time, then every NP-problem has a quasipolynomial time randomized algorithm with one-sided error. Further results concern the complexity of the problem, given \(C'\subseteq C\), to decide if \(C'=C\), and, given \(D'\subseteq D\), to decide if \(D'=D\). Applications to monotone relay circuits and game theory are pointed out.

MSC:

06E30 Boolean functions
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bioch, J. C.; Ibaraki, T., Complexity of identification and dualization of positive Boolean functions, Inform. and Comput, 123, 50-63 (1995) · Zbl 1096.68633
[3] Crama, Y., Dualization of regular Boolean functions, Discrete Appl. Math, 16, 79-85 (1987) · Zbl 0605.94011
[4] Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput, 24, 6, 1278-1304 (1995) · Zbl 0842.05070
[5] Fredman, M.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 618-628 (1996) · Zbl 0864.68038
[6] Gurvich, V., To theory of multistep games, USSR Comput. Math. Math. Phys, 13, 6, 1485-1500 (1973)
[7] Gurvich, V., Solvability of positional games in pure strategies, USSR Comput. Math. Math. Phys, 15, 2, 357-371 (1975)
[9] Jerrum, M. R.; Valiant, L. G.; Vazirani, V. V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci, 43, 169-188 (1986) · Zbl 0597.68056
[10] Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H., On generating all maximal independent sets, Inform. Process. Lett, 27, 119-123 (1988) · Zbl 0654.68086
[11] Karchmer, M.; Linial, N.; Newman, I.; Saks, M.; Widgerson, A., Combinatorial characterization of read-once formulae, Discrete Math, 114, 275-282 (1993) · Zbl 0781.06012
[13] Peled, U. N.; Simeone, B., An \(O\)(nm) - time algorithm for computing the dual of a regular Boolean function, Discrete Appl. Math, 49, 309-323 (1994) · Zbl 0802.90078
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.