Exponential bounds for DPLL below the satisfiability threshold
Exponential bounds for DPLL below the satisfiability threshold
复制标题
DPLL 的指数界限低于可满足性阈值
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Michael Molloy
中科院分区：
文献类型：
--
作者：
D. Achlioptas;P. Beame;Michael Molloy
对于每个 k ≤ 4，我们给出 τ k > 0，这样具有 n 个变量和 ⌊r k n⌋ 子句的随机 k-CNF 公式 F 可以高概率满足，但 ORDERED-DLL 在 F 上花费指数时间，并且具有一致的正概率。使用 [2] 的结果，对于某些自然回溯方案，这可以增强为高概率结果，并扩展到许多其他 DPLL 算法。
For each k ≤ 4, we give τ k > 0 such that a random k-CNF formula F with n variables and ⌊r k n⌋ clauses is satisfiable with high probability, but ORDERED-DLL takes exponential time on F with uniformly positive probability. Using results of [2], this can be strengthened to a high probability result for certain natural backtracking schemes and extended to many other DPLL algorithms.