Phase transition for Local Search on planted SAT
| dc.creator | Bulatov, Andrei A. | |
| dc.creator | Skvortsov, Evgeny S. | |
| dc.date | 2008-11-16 | |
| dc.date.accessioned | 2026-07-07T10:18:43Z | |
| dc.date.available | 2026-07-07T10:18:43Z | |
| dc.description | The Local Search algorithm (or Hill Climbing, or Iterative Improvement) is one of the simplest heuristics to solve the Satisfiability and Max-Satisfiability problems. It is a part of many satisfiability and max-satisfiability solvers, where it is used to find a good starting point for a more sophisticated heuristics, and to improve a candidate solution. In this paper we give an analysis of Local Search on random planted 3-CNF formulas. We show that if there is k<7/6 such that the clause-to-variable ratio is less than k ln(n) (n is the number of variables in a CNF) then Local Search whp does not find a satisfying assignment, and if there is k>7/6 such that the clause-to-variable ratio is greater than k ln(n)$ then the local search whp finds a satisfying assignment. As a byproduct we also show that for any constant r there is g such that Local Search applied to a random (not necessarily planted) 3-CNF with clause-to-variable ratio r produces an assignment that satisfies at least gn clauses less than the maximal number of satisfiable clauses. | |
| dc.description | 20 pages, 3 figures, submitted to a conference | |
| dc.identifier | https://arxiv.org/abs/0811.2546 | |
| dc.identifier | http://arxiv.org/abs/0811.2546 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/174284 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Logic in Computer Science | |
| dc.title | Phase transition for Local Search on planted SAT | |
| dc.type | text |