Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs

DOI10.1137/S0097539704440107zbMath1124.68041MaRDI QIDQ5422485

Eli Ben-Sasson, Michael Alekhnovich

Publication date: 22 October 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

SAT solvingrandom walk algorithmrandom CNFSAT heuristics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas, A comparative runtime analysis of heuristic algorithms for satisfiability problems, Completeness, approximability and exponential time results for counting problems with easy decision version, Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas, A Computing Procedure for Quantification Theory, The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems, Special issue in memory of Misha Alekhnovich. Foreword, Walksat Stalls Well Below Satisfiability

Uses Software

• Walksat