The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$

摘要: 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 number literals a clause. We also correlation between numbers clauses satisfied by pair assignments distance \(d=cn\), \(0 \le c 1\), \(((1-c)^r-1/2^r)/(1-1/2^r)\). The former quantity interest area landscape analysis as way better understand problems and assess their hardness for local search heuristics. [34], it has been shown may be calculated polynomial time any instance, its mean value over all instances was discussed. Our results are based on study variance assignment, covariance an arbitrary distance. As part study, closed-form formulas expected latter two quantities provided. Note relevant well.