Measures on SAT landscapes by statistical exploration of search trees

Stochastic local search methods are widely used for solving positive instances of NPhard problems. They are based on a partial exploration of a local search landscape characterized by a finite set, a fitness function and a neighborhood relation. We think that theoretical or experimental study of these landscapes, independently of search algorithms, could provide a better understanding of local search systems behaviour. In this paper, we propose a statistical method for measuring some parameters of landscapes. 1 For a given fitness value, our algorithm gives the number of points with this fitness, and produces a simple random sample of these points. As an example, we give estimates of local extrema proportion according to the fitness for some SAT landscapes. 1 Introduction Stochastic local search methods are widely used to solve positive instances of NP-hard problems. In formal terms, a stochastic local search system is a stochastic process following a trajectory in ..