What are easy regions for satisfiability? In other words, sufficient conditions for some SAT solver to be able to find a satisfying assignment, assuming it exists.One example is when each clause shares variables with few other clauses, due to constructive proof of LLL, any other results along those lines?There's sizable literature on easy regions for Belief Propagation, is there something along those lines for satisfiability?
Which SAT problems are easy?
cc.complexity theory;sat
I guess you know the classical result of Schaefer from STOC'78, but just in case.10.1145/800133.804350Schaefer proved that if SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in GF(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).