The threshold for random k-SAT is 2k log 2-O(k)
The threshold for random k-SAT is 2k log 2-O(k)
复制标题
DOI：
10.1090/s0894-0347-04-00464-3
复制
发表时间：
2004-01-01
影响因子：
3.9
通讯作者：
Peres, Y
中科院分区：
文献类型：
--
作者：
Achlioptas, D;Peres, Y
设随机CNF公式是从所有可能的变元子句中统一独立地选择而成的。众所周知，如果，则不能以趋于1的概率满足.我们证明了如果，其中，则是以趋于1的概率满足的。事实上，我们的技术为EVER产生了随机SAT阈值的一个显式下界。对于我们的边界，改进了所有以前已知的此类边界。参考文献
Letbe a random-CNF formula formed by selecting uniformly and independentlyout of all possible-clauses onvariables. It is well known that if, thenis unsatisfiable with probability that tends to 1 as. We prove that if, where, thenis satisfiable with probability that tends to 1 as. Our technique, in fact, yields an explicit lower bound for the random-SAT threshold for every. Forour bounds improve all previously known such bounds. References