Computational Aspects of Monotone Dualization

Kaz Makino

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.