DIMACS TR: 2006-01
On the Complexity of Monotone Boolean Duality Testing
Author: Khaled M. Elbassioni
We show that the duality of a pair of monotone Boolean functions in disjunctive normal forms can be tested in polylogarithmic time using a quasi-polynomial number of processors.
Our decomposition technique yields stronger bounds on the complexity of the problem than those currently known and also allows for generating all minimal transversals of a given hypergraph using only polynomial space.
Paper Available at:
DIMACS Home Page