The MAX-SAT limiting function conjecture
Let be a uniformly random -SAT formula with variables and clauses, and let
where denotes the maximum number of clauses simultaneously satisfied by an assignment. Fix and a constant .
MAX-SAT limiting function conjecture. For every and every constant , as ,
converges to a limit.
The conjecture concerns the existence of an asymptotic expected optimum for random MAX--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 is not.
References
- 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.