The satisfiability threshold conjecture for random k-SAT
Let be a uniformly random proper -SAT formula with variables and clauses, where each clause contains distinct variables, each possibly complemented, and clauses may be repeated. Write for this random formula, and let a property hold almost surely when its probability tends to as .
Satisfiability threshold conjecture. For each there exists a threshold density , such that for any positive , for all , is almost surely satisfiable, and for all , is almost surely unsatisfiable.
The conjecture asserts a sharp limiting satisfiability transition analogous to the known -SAT threshold. For large , satisfiability and unsatisfiability density bounds are asymptotically equal, but the existence of the threshold remains open in the source.
References
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
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.