Self-Duality of Bounded Monotone Boolean Functions and Related Problems

Abstract

In this paper we show the equivalence between the problem of determining self-duality of a boolean function in DNF and a special type of satisfiability problem called NAESPI. Eiter and Gottlob [ 8 ] use a result from [ 2 ] to show that self-duality of monotone boolean functions which have bounded clause sizes (by some constant) can be determined in polynomial time. We show that the self-duality of instances in the class studied by Eiter and Gottlob can be determined in time linear in the number of clauses in the input, thereby strengthening their result. Domingo [ 7 ] recently showed that self-duality of boolean functions where each clause is bounded by $ \left( {\sqrt {\log n} } \right) $ can be solved in polynomial time. Our linear time algorithm for solving the clauses with bounded size infact solves the $ \left( {\sqrt {\log n} } \right) $ bounded self-duality problem in $ O\left( {n^2 \sqrt {\log n} } \right) $ time, which is better bound then the algorithm of Domingo [ 7 ], O(n^3). Another class of self-dual functions arising naturally in application domain has the property that every pair of terms in f intersect in at most constant number of variables. The equivalent subclass of NAESPI is the c-bounded NAESPI. We also show that c-bounded NAESPI can be solved in polynomial time when c is some constant. We also give an alternative characterization of almost self-dual functions proposed by Bioch and Ibaraki [ 5 ] in terms of NAESPI instances which admit solutions of a ‘particular’ type.