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 the square root of (log n) can be solved in polynomial time. Our linear time algorithm for solving the clauses with bounded size infact solves the the square root of (log n) bounded self-duality problem in O(n{sup}2 (log n){sup}(1/2)) time, which is better bound then the algorithm of Domingo [7], O(n{sup}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.
展开▼
