Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time ∗†
Solving Random Satisfiable 3CNF Formulas in Expected Polynomial Time ∗†
复制标题
在预期多项式时间内求解随机可满足 3CNF 公式 ††
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
‡. Prof.MichaelKrivelevich
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;Dan Vilenchik;‡. Prof.MichaelKrivelevich
我们提出了一个算法来解决3SAT实例。几种算法已被证明工作whp（高概率）为各种SAT分布。然而，一个有效的whp算法有一个缺点。事实上，对于典型的例子，它工作得很好，但是对于一些罕见的输入，它根本没有提供解决方案。或者，可以要求算法总是产生正确的答案，但平均表现良好。期望多项式时间形式化了这个概念。我们证明了一些自然分布的3CNF公式，称为种植3SAT，我们的算法预期多项式（事实上，几乎线性）的运行时间。种植的3SAT分布是按以下方式生成的一组萨蒂斯的3CNF公式。首先，随机均匀地选取真值赋值。然后，它艾德的每个子句都以概率p包含在公式中。扩展以前的工作种植3SAT分布，我们提出，第一次为一个萨蒂斯的SAT分布，一个预期的多项式时间算法。也就是说，它解决了所有3SAT实例，并且在种植分布上（p = d/n 2，d > 0是一个足够大的常数），它在预期的多项式时间内运行。我们的结果推广到k-SAT的任何常数k。
We present an algorithm for solving 3SAT instances. Several algorithms have been proved to work whp (with high probability) for various SAT distributions. However, an algorithm that works whp has a drawback. Indeed for typical instances it works well, however for some rare inputs it does not provide a solution at all. Alternatively, one could require that the algorithm always produce a correct answer but perform well on average. Expected polynomial time formalizes this notion. We prove that for some natural distribution on 3CNF formulas, called planted 3SAT, our algorithm has expected polynomial (in fact, almost linear) running time. The planted 3SAT distribution is the set of satisfiable 3CNF formulas generated in the following manner. First, a truth assignment is picked uniformly at random. Then, each clause satisfied by it is included in the formula with probability p . Extending previous work for the planted 3SAT distribution, we present, for the first time for a satisfiable SAT distribution, an expected polynomial time algorithm. Namely, it solves all 3SAT instances, and over the planted distribution (with p = d/n 2 , d > 0 a sufficiently large constant) it runs in expected polynomial time. Our results extend to k -SAT for any constant k .