Computational Aspects of Monotone Dualization
Abstract: 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. We briefly survey computational
results for this problem, where we focus on the famous paper by
Fredman and Khachiyan (J.~Algorithms, 21:618--628, 1996), which showed
that the problem is solvable in quasi-polynomial time (and thus most
likely not \coNP-hard), as well as on follow-up works.