@inbook{c2cf5593c3e347019e3d58d338555696,
title = "A study of pure random walk on random satisfiability problems with {"}Physical{"} methods",
abstract = "The performances of a local search procedure, the Pure Random Walk (PRW), for the satisfiability (SAT) problem is investigated with statistical physics methods. We identify and characterize a dynamical transition for the behavior of PRW algorithm on randomly drawn SAT instances where, as the ratio of clauses to variables is increased, the scaling of the solving time changes from being linear to exponential in the input size. A framework for calculating relevant quantities in the linear phase, in particular the average solving time, is introduced, along with an approximate study of the exponential phase.",
author = "Guilhem Semerjian and R{\'e}mi Monasson",
year = "2004",
month = jan,
day = "1",
doi = "10.1007/978-3-540-24605-3\_10",
language = "English",
isbn = "3540208518",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "120--134",
editor = "Enrico Giunchiglia and Armando Tacchella",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
}