The MAX-SAT limiting function conjecture
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.
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
Sign in to submit a solution.
No solutions have been posted yet.