The satisfiability threshold conjecture for random k-SAT

Let FF be a uniformly random proper kk-SAT formula with nn variables and cncn clauses, where each clause contains kk distinct variables, each possibly complemented, and clauses may be repeated. Write F(n,cn)F(n,cn) for this random formula, and let a property hold almost surely when its probability tends to 11 as nn\rightarrow\infty.

Satisfiability threshold conjecture. For each kk there exists a threshold density ckc_k, such that for any positive ε\varepsilon, for all c<ckεc<c_k-\varepsilon, F(n,cn)F(n,cn) is almost surely satisfiable, and for all c>ck+εc>c_k+\varepsilon, F(n,cn)F(n,cn) is almost surely unsatisfiable.

The conjecture asserts a sharp limiting satisfiability transition analogous to the known 22-SAT threshold. For large kk, satisfiability and unsatisfiability density bounds are asymptotically equal, but the existence of the threshold remains open in the source.

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).

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.