Computational aspects of monotone dualization: A brief survey

Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and Game Theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 25 years. In this paper, we briefly survey computational results for this problem, where we focus on the famous paper by Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628], which showed that the problem is solvable in quasi-polynomial time (and thus most likely not co-NP-hard), as well as on follow-up works. We consider computational aspects including limited nondeterminism, probabilistic computation, parallel and learning-based algorithms, and implementations and experimental results from the literature. The paper closes with open issues for further research. (C) 2007 Elsevier B.V. All rights reserved.