Random -SAT satisfiability threshold conjecture
Random -SAT satisfiability threshold conjecture
For given , , and , let be the random -SAT formula obtained by including each of the possible -clauses independently with probability . Satisfiability conjecture. For each , there exists such that for every :
- if , then with high probability is satisfiable;
- if , then with high probability is unsatisfiable.
This asserts a sharp satisfiability threshold at the stated scale, a central problem in random constraint satisfaction and average-case complexity. The supplied text does not report a resolution.
Sources & referencesView supporting material
Primary source
Will Perkins, “Searching for (sharp) thresholds in random structures: where are we now?”, arXiv:2401.01800 (2024).
Additional references
2 papers in this index state this conjecture (2022–2024). The statement above is taken from the most recent of them; the others are arXiv:2204.06615.
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.