The maximum-satisfiable-clauses scaling conjecture for random K-SAT
The maximum-satisfiable-clauses scaling conjecture for random K-SAT
Let be the maximum number of clauses that can be satisfied by one assignment of variables in a random K-SAT instance with clauses, and let be the threshold from the linear phase transition conjecture. Maximum-SAT scaling conjecture. Assuming the linear phase transition conjecture holds, for every the limit
exists and is smaller than one. This conjecture concerns the limiting fraction of clauses satisfiable above the threshold; the source attributes it to earlier work and does not report a resolution.
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
David Gamarnik, “Linear Phase Transition in Random Linear Constraint Satisfaction Problem”, arXiv:math/0210470 (2003).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.