Random kk-SAT satisfiability threshold conjecture

For given nn, k2k\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 k2k\geq2, there exists ck>0c_k>0 such that for every ε>0\varepsilon>0:

  • if p(1ε)ckn1/(k1)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+ε)ckn1/(k1)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.

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

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.