Phase transition for Local Search on planted SAT

Details Phase transition for Local Search on planted SAT Phase transition for Local Search on planted SAT

2008-11-16

arxiv.org/abs/0811.2546v1

Computer Science

Data Structures and Algorithms

20 pages, 3 figures, submitted to a conference

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Phase transition for Local Search on planted SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase transition for Local Search on planted SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transition for Local Search on planted SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-330884