The threshold for random k-SAT is 2^k log 2 - O(k)
By Dimitris Achlioptas, Yuval Peres. 2004
109 citations recorded by the source corpus.
Let F k ( n, m ) be a random k -CNF formula formed by selecting uniformly and independently m out of all possible k -clauses on n variables. It is well-known that if r ≥ 2 k log 2, then F k ( n, rn ) is unsatisfiable with probability that tends to 1 as n → ∞ . We prove that if r ≤ 2 k log 2 − t k , where t k = O ( k ), then F k ( n, rn ) is satisfiable with probability that tends to 1 as n → ∞ . Our technique, in fact, yields an explicit lower bound for the random k -SAT threshold for every k . For k ≥ 4 our bounds improve all previously known such bounds.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/b4d64fe635e6fb54f85cc4edd5f31a53743b7a95
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Networks and Communications
Citations in the corpus
- On the solution-space geometry of random constraint satisfaction problems (2006, methodology): “Hence the need for the second moment method [2, 4].”