Estimating the Number of Local Maxima for k-SAT Instances

Abstract

We explore the applicability of a sampling method devised by J. Garnier and L. Kallel (SIAM J. Discrete Math., 2002) to approximate the number of local maxima in search spaces induced by k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. Although the problem setting for k-SAT instances does not meet all pre-conditions required by the Garnier/Kallel-approach, we obtain approximations of the number of local maxima within the same order of magnitude as the exact values that have been determined by complete search. Since the comparison requires calculation of the complete --set of local maxima, only small k-SAT instances have --been considered so far. Furthermore, we outline a method for obtaining upper bounds for the average number of local maxima in k-SAT instances, which shows changes in the average number around the phase transition threshold.