Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time
复制标题
在几乎多项式时间内确定性搜索 CNF 满足分配
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
R. Servedio;Li
我们考虑的基本去随机化问题的确定性找到一个满意的CNF公式，有许多满意的分配。我们给出了一个确定性算法，给定一个至少有2^n个满足赋值的n变量poly（n）子句CNF公式，该算法在时间[ n^{ ilde{O}（loglog n）^2} ]，并给出了F的一个满意的赋值.在我们的工作之前，这个问题的最快已知算法是简单地枚举CNF的伪随机生成器的所有种子;使用CNF的最佳已知PRG引用{DETT 10，这需要时间n^{ ilde{}（log n）}，即使是常数。我们的方法是基于一个新的一般框架，确定性搜索和确定性近似计数，我们相信可能会找到进一步的应用。
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable poly(n)-clause CNF formula F that has at least ≥ 2^n satisfying assignments, runs in time [ n^{ ilde{O}(loglog n)^2} ] for ≥ ge 1/polylog(n) and outputs a satisfying assignment of F. Prior to our work the fastest known algorithm for this problem was simply to enumerate over all seeds of a pseudorandom generator for CNFs; using the best known PRGs for CNFs cite{DETT10, this takes time n^{ ilde{Ω}(log n)} even for constant ≥. Our approach is based on a new general framework relating deterministic search and deterministic approximate counting, which we believe may find further applications.