Daniel Berend

In this paper we show that the so-called normalized auto- correlation length of random Max r-Sat converges in probability to (1 − 1/2^r)/r, where r is the number of literals in a clause. We also show that the correlation between the numbers of clauses satisfied by a random pair of assignments of distance d = cn, 0 ≤ c ≤ 1, converges in probability to ((1 − c)^r − 1/2^r)/(1 − 1/2^r). The former quantity is of interest in the area of landscape analysis as a way to better understand problems and assess their hardness for local search heuristics. In [34], it has been shown that it may be calculated in polynomial time for any instance, and its mean value over all instances was discussed. Our results are based on a study of the variance of the number of clauses satisfied by a random assignment, and the covariance of the numbers of clauses satisfied by a random pair of assignments of an arbitrary distance. As part of this study, closed-form formulas for the expected value and vari- ance of the latter two quantities are provided. Note that all results are relevant to random r-Sat as well.