The Normalized Autocorrelation Length of Random Max \(r\)-Sat Converges in Probability to \((1-1/2^r)/r\) Academic Article uri icon

abstract

  • In this paper we show that the so-called normalized autocorrelation 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 \le c \le 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 variance of the latter two quantities are provided. Note that all results are relevant to random \(r\)-Sat as well.

publication date

  • January 1, 2016