← All problems

The linear phase transition conjecture for random K-SAT

24 years old · traced to

A random K-SAT instance has nn Boolean variables and m=cnm=cn clauses, where cc is the clause-to-variable ratio and KK is the number of literals per clause. The linear phase transition conjecture. For every K≥2K\geq 2 there exists a constant cK∗c^*_K such that a random K-SAT formula is satisfiable when c<cK∗c<c^*_K and is not satisfiable when c>cK∗c>c^*_K, with high probability as n→∞n\to\infty. Equivalently, satisfiability undergoes a linear sharp phase transition at m=cK∗nm=c^*_Kn. The sharp phase transition is known in a more general setting, and the case K=2K=2 is solved with c2∗=1c^*_2=1; the existence of the linear threshold for higher KK is the outstanding part of the conjecture.

References
  1. David Gamarnik, “Linear Phase Transition in Random Linear Constraint Satisfaction Problem”, arXiv:math/0210470 (2003).

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.