Self-Duality of Bounded Monotone Boolean Functions and Related Problems Authors: Daya Ram Gaur and Ramesh Krishnamurti. Source: Lecture Notes in Artificial Intelligence Vol. 1968, 2000, 209 - 223. 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 (√log n) can be solved in polynomial time. Our linear time algorithm for solving the clauses with bounded size infact solves the (√log n) bounded self-duality problem in O(n2 √log n) time, which is better bound then the algorithm of Domingo [7], O(n3). 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 cis 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. ©Copyright 2000 Springer