The maximum-satisfiable-clauses scaling conjecture for random K-SAT

From papers

Let N(n,m)N(n,m) be the maximum number of clauses that can be satisfied by one assignment of nn variables in a random K-SAT instance with mm clauses, and let cKc^*_K be the threshold from the linear phase transition conjecture. Maximum-SAT scaling conjecture. Assuming the linear phase transition conjecture holds, for every c>cKc>c^*_K the limit

limnN(n,cn)cn\lim_{n\rightarrow\infty}{N(n,cn)\over cn}

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

No solutions have been posted yet.