Probabilistic characterization of random Max r-Sat

摘要

In this paper we provide a probabilistic characterization of the random Max r-Sat problem. We study 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. Closed-form formulas for the expected value and the variance of these quantities are provided. We asymptotically and probabilistically analyze these formulas and use them to gain insights on the similarity of instances.