Algorithms for four variants of the exact satisfiability problem

We present four polynomial space and exponential time algorithms for variants of the E S problem. First, an O(1.1120ⁿ) (where n is the number of variables) time algorithm for the NP-complete decision problem of E 3-S , and then an O(1.1907ⁿ) time algorithm for the general decision problem of E S . The best previous algorithms run in O(1.1193ⁿ) and O(1.2299ⁿ) time, respectively. For the #P-complete problem of counting the number of models for E 3-S we present an O(1.1487ⁿ) time algorithm. We also present an O(1.2190ⁿ) time algorithm for the general problem of counting the number of models for E S ; presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix.