The satisfiability threshold conjecture for random k-SAT
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.