Random kk-SAT satisfiability threshold conjecture

About 4 years old · traced to

For given nn, k≥2k\geq2, and pp, let Fk(n,p)F_k(n,p) be the random kk-SAT formula obtained by including each of the (2nk)\binom{2n}{k} possible kk-clauses independently with probability pp. Satisfiability conjecture. For each k≥2k\geq2, there exists ck>0c_k>0 such that for every ε>0\varepsilon>0:

  • if p≤(1−ε)ckn−1/(k−1)p\leq(1-\varepsilon)c_kn^{-1/(k-1)}, then with high probability Fk(n,p)F_k(n,p) is satisfiable;
  • if p≥(1+ε)ckn−1/(k−1)p\geq(1+\varepsilon)c_kn^{-1/(k-1)}, then with high probability Fk(n,p)F_k(n,p) 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.

References

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

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.