The MAX-SAT and SAT equivalence conjecture

From papers

Let F(n,cn)F(n,cn) be a uniformly random kk-SAT formula with nn variables and cncn clauses, and let f(n,cn)f(n,cn) denote the expected maximum number of satisfiable clauses. For a fixed density cc, consider the limiting expected satisfiable fraction and the limiting probability of satisfiability.

MAX-SAT and SAT equivalence conjecture. For any c<0c<0,

limnf(n,cn)cn=1\lim_{n\rightarrow\infty}\frac{f(n,cn)}{cn}=1

if and only if

limnPr(F(n,cn) is satisfiable)=1.\lim_{n\rightarrow\infty}\Pr\bigl(F(n,cn)\ \operatorname{is\ satisfiable}\bigr)=1.

The conjecture is intended to formalize a connection between the MAX-SAT limiting function conjecture and the usual satisfiability threshold conjecture. The source provides no resolution status beyond presenting it as a conjecture.

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

No solutions have been posted yet.