It’s All about the Support: A New Perspective on the Satisfiability Problem

Abstract

We study a new approach to the satisfiability problem, which we call the Support Paradigm. Given a CNF formula F and an assignment to its variables we say that a literal x supports a clause C in F w.r.t. ψ if x is the only literal that evaluates to true in C. Our focus in this work will be on heuristics that obey the following general template: start at some assignment to the variables, then iteratively, using some predefined (greedy) rule, try to minimize the number of unsatisfied clauses (or the distance from some satisfying assignment) until a satisfying assignment is reached. We say that such a heuristic is part of the Support Paradigm if the greedy rule uses the support as its main criterion. We present a new algorithm in the Support Paradigm and rigorously prove its effectiveness for a certain distribution over satisfiable k-CNF formulas known as the planted distribution. One motivation for this work is recent experimental results showing that some simple variants of the RWalkSAT algorithm, which base their greedy rule on the support, seem to remain e ective for random 3CNF formulas in the “hard” near-threshold regime, while for example RWalkSAT, which disregards the support, is already inefficient in a much earlier stage.