Average Case Self-Duality of Monotone Boolear Functions

摘要

The problem of determining whether a monotone boolean function is self-dual has numerous applications in Logic and AI. The applications include theory revision, model-based diagnosis, abductive explanations and learning monotone boolean functions. It is not known whether self-duality of monotone boolean functions can be tested in polynomial time, though a quasi-polynomial time algorithm exists. We describe another quasi-polynomial time algorithm for solving the self-duality problem of monotone boolean functions and analyze its average-case behaviour on a set of randomly generated instances.