Solving SAT efficiently with promises
In this paper, we consider two types of promises for (k-)CNF formulas which can help to find a satisfying assignment of a given formula. The first promise is the Hamming distance between truth assignments. Namely, we know in advance that a k-CNF formula with n variables, if satisfiable, has a satisfying assignment with at most pn variables set to 1. Then we ask whether or not the formula is satisfiable. It is shown that for k greater than or equal to 2 and (i) when p = n(c) (-1 < c less than or equal to 0), the problem is NP-hard; and (ii) when p log n/n, there exists a polynomial-time deterministic algorithm. The algorithm is based on the exponential-time algorithm recently presented by Schoning [7]. It is also applied for coloring k-uniform hypergraphs. The other promise is the number of satisfying assignments. For a CNF formula having 2(n)/2(nepsilon) (0 less than or equal to epsilon < 1) satisfying assignments, we present a subexponential-time deterministic algorithm based on the inclusion-exclusion formula.
sat promise cnf formula inclusion-exclusion solution-density