2006-01: On the Complexity of Monotone Boolean Duality Testing

DIMACS TR: 2006-01

On the Complexity of Monotone Boolean Duality Testing

Author: Khaled M. Elbassioni

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-01.ps.gz

DIMACS Home Page