MEASURES AND ALGORITHMS FOR THE EXACT SATISFIABILITY PROBLEM AND ITS VARIANTS

Abstract

In this thesis, we study the Exact Satisfiability problem and its variants. The 5 problems that are studied are: Exact Satisfiability (XSAT) and General k Exact Satisfiability problems (Decision), #X3SAT (Counting), Max Hamming Distance XSAT and Max Hamming Distance X3SAT (Optimization problems). These problems are at least NP-hard. We propose faster exact algorithms to solve these problems, beating the current state of the art algorithms. We either design a new algorithm using a nonstandard measure, or stick to the standard measure and use other nontrivial results to aid us.