New Results on Monotone Dualization and Generating Hypergraph Transversals
Preprint
Abstract
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time respectively output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with O(log^2 n) suitably guessed bits). This result sheds new light on the complexity of this important problem.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Molecular Computing, Bounded Nondeterminism, and Efficient RecursionAlgorithmica, 1999
- A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean FunctionsJournal of Algorithms, 1998
- On the Complexity of Dualization of Monotone Disjunctive Normal FormsJournal of Algorithms, 1996
- Exact Transversal Hypergraphs and Application to Boolean μ-FunctionsJournal of Symbolic Computation, 1994
- An O(nm)-time algorithm for computing the dual of a regular Boolean functionDiscrete Applied Mathematics, 1994
- Coherent Structures and Simple Games1990
- On generating all maximal independent setsInformation Processing Letters, 1988
- A theory of diagnosis from first principlesArtificial Intelligence, 1987
- Dualization of regular Boolean functionsDiscrete Applied Mathematics, 1987
- Design by example: An application of Armstrong relationsJournal of Computer and System Sciences, 1986