Behavior of heuristics on large and hard satisfiability problems
2006 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, no 3, 037702- p.Article in journal (Refereed) Published
We study the behavior of a heuristic for solving random satisfiability problems by stochastic local search near the satisfiability threshold. The heuristic for average satisfiability (ASAT), is similar to the Focused Metropolis Search heuristic, and shares the property of being focused, i.e., only variables in unsatisfied clauses are updated in each step. It is significantly simpler than the benchmark WALKSAT heuristic. We show that ASAT solves instances as large as N=10(6) in linear time, on average, up to a ratio of 4.21 clauses per variable in random three-satisfiability. For K higher than 3, ASAT appears to solve instances of K-satisfiability up to the Montanari-Ricci-Tersenghi-Parisi full replica symmetry breaking (FSRB) threshold denoted alpha(s)(K) in linear time.
Place, publisher, year, edition, pages
2006. Vol. 74, no 3, 037702- p.
Atomic physics, Benchmarking, Problem solving, Quantum theory, Random processes
IdentifiersURN: urn:nbn:se:kth:diva-8491DOI: 10.1103/PhysRevE.74.037702ISI: 000240870300105ScopusID: 2-s2.0-33748771720OAI: oai:DiVA.org:kth-8491DiVA: diva2:13830
QC 201009012008-05-192008-05-192010-09-01Bibliographically approved