A satisfiability algorithm for AC0
A satisfiability algorithm for AC0
复制标题
AC0 的可满足性算法
DOI：
10.1137/1.9781611973099.77
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Paturi
中科院分区：
文献类型：
--
作者：
R. Impagliazzo;W. Matthews;R. Paturi
我们考虑有效枚举对 AC0 电路的满意分配的问题。我们给出了一种零误差随机算法，该算法以 AC0 电路作为输入，并构造一组限制，对 {0, 1}n 进行划分，以便在每个限制下电路的值是恒定的。设 d 表示电路的深度，cn 表示门的数量。该算法在时间 |C|2n(1-μc,d) 内运行，其中 |C|是 μc,d>1/O[lg c + g lg d]d&minus1 的电路大小，概率至少为 1−2−n。
因此，我们得到了改进的指数时间算法，用于 AC0 电路可满足性和计数解决方案。此外，我们还得到了 AC0 电路与奇偶校验相关性的改进界限。
作为我们分析的重要组成部分，我们扩展了 Hastad 切换引理以处理多个 k-cnfs 和 k-dnfs。
We consider the problem of efficiently enumerating the satisfying assignments to AC0 circuits. We give a zero-error randomized algorithm which takes an AC0 circuit as input and constructs a set of restrictions which partitions {0, 1}n so that under each restriction the value of the circuit is constant. Let d denote the depth of the circuit and cn denote the number of gates. This algorithm runs in time |C|2n(1-μc,d) where |C| is the size of the circuit for μc,d>1/O[lg c + g lg d]d&minus1 with probability at least 1−2−n.
As a result, we get improved exponential time algorithms for AC0 circuit satisfiability and for counting solutions. In addition, we get an improved bound on the correlation of AC0 circuits with parity.
As an important component of our analysis, we extend the Hastad Switching Lemma to handle multiple k-cnfs and k-dnfs.