Optimal myopic algorithms for random 3-SAT
Optimal myopic algorithms for random 3-SAT
复制标题
随机 3-SAT 的最佳近视算法
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
G. Sorkin
中科院分区：
文献类型：
--
作者：
D. Achlioptas;G. Sorkin
设F/sub 3/（n，m）是一个随机3-SAT公式，它是从n个变量上的所有8个（/sup n/C/sub 3/）可能的3-子句中均匀地、独立地、有替换地选择m个子句而形成的.证明了存在一个常数r/sub 3/使得对任意的/spl epsiv/>0，F/sub 3/[n，（r/sub 3/-/spl epsiv/）n]几乎必然可满足，而F/sub 3/[n，（r/sub 3/+/spl epsiv/）n]几乎必然不可满足. r/sub 3/的潜在值的最佳下界来自分析单位子句传播的相当简单的扩展。它是由D。Achlioptas（2000）认为，所有这些扩展都可以在一个共同的框架中进行，并通过采用微分方程以统一的方式进行分析。我们确定了在这个框架中可表达的最优算法，建立了r/sub 3/>3.26。我们通过微分方程扩展分析，并广泛使用一个新的优化问题，我们称之为“最大密度多选择背包”问题。最优背包解决方案的结构优雅地表征了最优算法所做的选择。
Let F/sub 3/(n,m) be a random 3-SAT formula formed by selecting uniformly, independently and with replacement, m clauses among all 8(/sup n/C/sub 3/) possible 3-clauses over n variables. It has been conjectured that there exists a constant r/sub 3/ such that, for any /spl epsiv/>0, F/sub 3/[n,(r/sub 3/-/spl epsiv/)n] is almost surely satisfiable, but F/sub 3/[n,(r/sub 3/+/spl epsiv/)n] is almost surely unsatisfiable. The best lower bounds for the potential value of r/sub 3/ have come form analyzing rather simple extensions of unit-clause propagation. It was shown by D. Achlioptas (2000) that all these extensions can be cast in a common framework and analyzed in a uniform manner by employing differential equations. We determine optimal algorithms that are expressible in that framework, establishing r/sub 3/>3.26. We extend the analysis via differential equations, and make extensive use of a new optimization problem that we call the "max-density multiple-choice knapsack" problem. The structure of optimal knapsack solutions elegantly characterizes the choices made by an optimal algorithm.