## Abstract

Given the prime conjunctive normal form (CNF) representation φ of a monotone Boolean function f: {0, 1}^{n} → {0, 1}, the dualization problem calls for finding the corresponding prime disjunctive normal form representation ψ of d. A very simple method works by multiplying out the clauses of φ from left to right in some order, simplifying whenever possible by using the absorption law. We show that for any monotone CNF φ, left-to-right multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNFs such as those with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.

Original language | British English |
---|---|

Pages (from-to) | 3424-3439 |

Number of pages | 16 |

Journal | SIAM Journal on Computing |

Volume | 39 |

Issue number | 7 |

DOIs | |

State | Published - 2010 |

## Keywords

- Dualization
- Enumerating minimal hypergraph transversals
- Monotone Boolean function