The MAX-SAT limiting function conjecture

About 23 years old · traced to

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(max⁡Fk(n,m)),f_k(n,m)=\mathbb{E}(\max F_k(n,m)),

where max⁡Fk(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 n→∞n\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.