A Note on Approximate Counting for k-DNF
A Note on Approximate Counting for k-DNF
复制标题
关于 k-DNF 近似计数的注释
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
L. Trevisan
我们描述了一种确定性算法，对于常数k，给定k- dnf或k- cnf公式φ和参数e，以φ的大小和1/e的多项式（但k的双指数）在时间上线性运行，并返回φ满足分配的分数的估计，直至加性误差e。这比以前的多项式（但超线性）时间算法有所改进。该算法使用一个简单的递归过程，它不是基于非随机化技术。它类似于Hirsch为解决k-SAT相关问题而提出的一种算法，该算法保证了作业的e分数是令人满意的。我们的分析与赫希的分析不同（而且比赫希的分析更简单）。
We describe a deterministic algorithm that, for constant k, given a k-DNF or k-CNF formula φ and a parameter e, runs in time linear in the size of φ and polynomial in 1/e (but doubly exponential in k) and returns an estimate of the fraction of satisfying assignments for φ up to an additive error e. This improves over previous polynomial (but super-linear) time algorithms. The algorithm uses a simple recursive procedure and it is not based on derandomization techniques. It is similar to an algorithm by Hirsch for the related problem of solving k-SAT under the promise that an e-fraction of the assignments are satisfying. Our analysis is different from (and somewhat simpler than) Hirsch’s.