SAT local search algorithms: Worst-case study

DOI10.1023/A:1006318521185zbMath0967.68146OpenAlexW1500660230MaRDI QIDQ1977754

Edward A. Hirsch

Publication date: 3 September 2001

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1006318521185

zbMATH Keywords

local search algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (8)

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ UnitWalk: A new SAT solver that uses local search guided by unit clause elimination ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ A Theoretical Analysis of Search in GSAT ⋮ Hard satisfiable instances for DPLL-type algorithms ⋮ A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

This page was built for publication: SAT local search algorithms: Worst-case study