The MAX-SAT limiting function conjecture

From papers

Let Fk(n,m)F_k(n,m) be a uniformly random kk-SAT formula with nn variables and mm clauses, and let

fk(n,m)=E(maxFk(n,m)),f_k(n,m)=\mathbb{E}(\max F_k(n,m)),

where maxFk(n,m)\max F_k(n,m) denotes the maximum number of clauses simultaneously satisfied by an assignment. Fix kk and a constant c>0c>0.

MAX-SAT limiting function conjecture. For every kk and every constant c>0c>0, as nn\rightarrow\infty,

fk(n,cn)n\frac{f_k(n,cn)}{n}

converges to a limit.

The conjecture concerns the existence of an asymptotic expected optimum for random MAX-kk-SAT. The source says it extends naturally to arbitrary CSPs and is open even for MAX-2-SAT; monotonicity in the clause density is known, but monotonicity in nn is not.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi and Gregory B. Sorkin, “Random MAX SAT, Random MAX CUT, and Their Phase Transitions”, arXiv:math/0306047 (2003).

Solutions 0

No solutions have been posted yet.