Lower bounds for random 3-SAT via differential equations
Lower bounds for random 3-SAT via differential equations
复制标题
DOI：
10.1016/s0304-3975(01)00159-1
复制
发表时间：
2001-08-28
影响因子：
1.1
通讯作者：
Achlioptas, D
中科院分区：
文献类型：
--
作者：
Achlioptas, D
人们普遍认为，随机k-SAT公式的可满足性概率作为其子句变量比的函数呈现出一个尖锐的阈值。对于研究最多的情况，k=3，在过去十年中已经有许多结果提供了阈值的潜在位置的上界和下界。这条线索中的所有下界都是算法的，即在每种情况下，如果子句与变量的比率低于某个值，则一个特定的算法以概率1-O(1)满足3-SAT的随机实例。我们展示了通过以简单、统一的方式重新推导大多数已知的随机3-SAT的下界，微分方程组可以作为分析这类算法的通用工具。(C)2001 Elsevier Science B.V.保留所有权利。
It is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k = 3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i.e., in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1 - o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner. (C) 2001 Elsevier Science B.V. All rights reserved.