1

Abstract. There has been considerable research interest into the sol-ubility phase transition, and its eect on search cost for backtracking algorithms. In this paper we show that a similar easy-hard-easy pattern occurs for local search, with search cost peaking at the phase transition. This is despite problems beyond the phase transition having fewer solu-tions, which intuitively should make the problems harder to solve. We examine the relationship between search cost and number of solutions at dierent points across the phase transition, for three dierent local search procedures, across two problem classes (CSP and SAT). Our nd-ings show that there is a signicant correlation, which changes as we move through the phase transition