Satisfiability and self-duality of monotone boolean functions
Ramiesh Krishnamurti, Daya Ram Gaur · 1999
The problem of determining if a given monotone boolean function is self-dual arises in the areas of artificial intelligence, databases, boolean circuits, graph theory, digital signal analysis, graph theory to name a few. The problem has received considerable attention and the exact complexity of the problem is open to the best of our knowledge. One of the initial conjectures that the problem is Co-NP-Complete was answered in the negative by Fredman and Khachiyan [19] who demonstrated the existence of a On4olog n+O1 for solving the problem. Recent attempts at proving that the problem is in P have met with little success. The exact relationship with other problems such as graph isomorphism is also not known. Furthermore no non-trivial lower bounds are known on the running times of the algorithms for this problem. In this thesis we formulate and study a special type of the Not All Equal Satisfiability Problem (NAESPI) which is equivalent to self-duality. We exhibit polynomial time algorithms for solving several restricted versions of NAESPI which arise naturally in differing application domains. We describe a simple On2log n+2 algorithm for NAESPI problem whose performance can be improved to On4olog n+O1 (by using the observations of Fredman and Khachiyan). We study the average case behaviour of our algorithm and show that on average the algorithm terminates in maxcOpn3.87p ,Opn3log 2 np,Op 1p- 1p p2+oplog 1p-1 pp c time, where p is the probability with which the instance is generated. We also describe an approximation algorithm for a generalization of the problem (which corresponds to a generalization of the MAX-CUT problem and is equivalent to hypergraph 2-coloring).