WalkSAT is Linear on Random 2-SAT
- 3 October 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (4) , 1939-1952
Abstract
In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (CO 646/3, CO 646/5, CO 646/6)
- Deutsche Forschungsgemeinschaft (CO 646/6)
- Deutsche Forschungsgemeinschaft (491453517)
- Deutsche Forschungsgemeinschaft (411362735)
This publication has 22 references indexed in Scilit:
- The number of satisfying assignments of random 2‐SAT formulasRandom Structures & Algorithms, 2021
- The asymptotic k-SAT thresholdAdvances in Mathematics, 2016
- Rigorous location of phase transitions in hard optimization problemsNature, 2005
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)Journal of the American Mathematical Society, 2004
- Lower bounds for random 3-SAT via differential equationsTheoretical Computer Science, 2001
- Local Search Algorithms for SAT: An Empirical EvaluationJournal of Automated Reasoning, 2000
- Random Graphs2000
- A Threshold for UnsatisfiabilityJournal of Computer and System Sciences, 1996
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- Randomized Algorithms1995