Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression
复制标题
具有加权对称门的有界深度电路：可满足性、下限和压缩
DOI：
10.1016/j.jcss.2019.04.004
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Teruyama Junichi
中科院分区：
文献类型：
--
作者：
Sakai Takayuki;Seto Kazuhisa;Tamaki Suguru;Teruyama Junichi
摘要一个布尔函数f：{0，1}n→{0，1}是加权对称的，如果存在函数g：z→{0，1}和整数w0，w1，…，wn使得f(x 1，…，xn)=g(w0+∑i=1 nwi xi)成立。本文给出了具有AND、OR、NOT门和有限个加权对称门的有界深度电路的电路可满足性问题的算法。我们的算法在时间上以超多项式快于2n，即使在门的数目是超多项式并且对称门的最大权重接近指数时也是如此。作为特例，我们给出了具有n个变量和O(N T)子句的情形的时间Poly(N T)⋅2 n−n 1/O(T)的最大可满足性问题的一个算法.通过对算法的分析，我们给出了这类电路的平均下界和压缩算法，以及这类电路多数投票的最坏情况下界。
Abstract A Boolean function f:{0, 1} n→{0, 1} is weighted symmetric if there exist a function g: Z→{0, 1} and integers w 0, w 1,…, w n such that f (x 1,…, x n)= g (w 0+∑ i= 1 n w i x i) holds. In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, OR, NOT gates and a limited number of weighted symmetric gates. Our algorithms run in time super-polynomially faster than 2 n even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in time poly (n t)⋅ 2 n− n 1/O (t) for instances with n variables and O (n t) clauses. Through the analysis of our algorithms, we show average-case lower bounds and compression algorithms for such circuits and worst-case lower bounds for majority votes of such circuits.