Computational aspects of monotone dualization: A brief survey
| Autor: | Thomas Eiter, Kazuhisa Makino, Georg Gottlob |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Self-duality
Limited nondeterminism Dualization Hypergraph Theoretical computer science Monotonic function Hypergraphs Independent sets Discrete Mathematics and Combinatorics Monotone Boolean functions Conjunctive normal form Boolean function Hitting sets Time complexity Mathematics Discrete mathematics Polynomial-total time Output-polynomial algorithms Applied Mathematics Probabilistic logic Set coverings Monotone polygon Transversals Quasi-polynomial time Combinatorial enumeration Game theory |
| Zdroj: | Discrete Applied Mathematics. 156:2035-2049 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2007.04.017 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect