On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions (Q1961461)

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.