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  use a result from  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  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 , 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  in terms of NAESPI instances which admit solutions of a `particular' type.
©Copyright 2000 Springer