Name
Abstract | ||
|---|---|---|
We study a new approach to the satisabilit y 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 predened (greedy) rule, try to minimize the number of unsatised 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 eectiv eness for a certain distribution over satisable 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 eectiv e for random 3CNF formulas in the \hard" near-threshold regime, while for example RWalkSAT, which disregards the support, is already inecien t in a much earlier stage. |
Year | Venue | Keywords |
|---|---|---|
2007 | JSAT | random k-sat,ecient heuristics,average case analysis,computational complexity |
Field | DocType | Volume |
Discrete mathematics,Heuristic,Boolean satisfiability problem,Theoretical computer science,Heuristics,Mathematics,Computational complexity theory | Journal | 3 |
Issue | Citations | PageRank |
3-4 | 1 | 0.39 |
References | Authors | |
17 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan Vilenchik | 1 | 143 | 13.36 |