Dualization (TL;DR)

Here is a 5 sentences survey on the dualization of monotone Boolean functions, and its generalizations, through the different shapes it takes on (hyper)graphs and lattices.

Go back to the long version here.

---

In its most simple terms, the dualization of monotone Boolean functions amounts to decide, given a positive CNF $\varphi$ and a positive DNF $\psi$, whether $\varphi=\psi$. In its generation versions, only one of the two formulas is provided, and the other (of minimum size) is to be computed. This problem is ubiquitous in many areas of computer science [EG95] and the best known algorithm due to Fredman and Khachiyan [FK96] solves it in quasi-polynomial time (or incremental quasi-polynomial time for the generation version). Breaking the quasi-polynomial time barrier is one of the most challenging open question in enumeration theory [EGM08].

Since then, it has been shown to be equivalent (or a particular case) of various enumeration problems in graphs, hypergraphs, and lattices, such as:

• minimal dominating sets enumeration;
• minimal transversal enumerations;
• maximal independent sets enumeration;
• database repairs enumeration;
• lattice dualization;
• characteristic models and horn clauses translation;
• meet-irreducible and implicational bases translation;
• etc.