Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms
复制标题
ACC 电路稀疏对称函数的下界：扩展范围
DOI：
10.1007/s00224-022-10106-8
复制
发表时间：
2020
影响因子：
0.5
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
Nikhil Vyas;Ryan Williams
我们继续通过电路满意度算法证明电路下限的程序。 } \ text { - } \ Mathsf {np} = \ Mathsf {ntime} [n^{（\ log n）^{o（1）}}] $，其他复杂性类别没有小电路（在最坏情况下和/或平均）来自各种电路类C $ \ Mathcal {C} $，通过表明C $ \ Mathcal {C} $允许非平凡满意度和/或＃SAT算法，这些算法以少量的数量击败了详尽的搜索。在本文中，我们提出了一个新的强下限后果，它使得c $ {\ mathcal c}的非平凡＃SAT算法说对称性布尔函数f（x _1，…，x _ n ）如果它在O（1）的值上输出1 ∑ i x i $ {\ sum} _ {i} x_ {i} $，我们向每个稀疏F表示，以及所有“典型” c $ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {i} _ {i} Mathcal {c} $，更快的＃c $ \ Mathcal {C} $电路的SAT算法意味着与电路类F c $ f \ c $ f \ circs \ Mathcal {c} $相对强的下限，这可能比C $ \ Mathcal强{C} $本身。 ∘c）$（f \ Circ \ Mathcal {C}）$ -CIRCUITS多项式大小。 $ - 以2 n -nε$ 2^{n -n^{{\ varepsilon}}}} $ time（某些ε> 0）表示q u a s i -n p没有（f \ c）$（f \ circ \ circ \ circ \多项式大小的数学{C}）$ - 循环。 “确切的多数”功能，改善了以前的c ^0 [Williams jacm'14]和c c ^0∘t h r [Williams Stoc'14]，[Murray-Williams stoc'18]。反对这样的电路类。
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in Quasi - NP = NTIME [ n ( log n ) O ( 1 ) ] $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes C $\mathcal { C}$ , by showing that C $\mathcal { C}$ admits non-trivial satisfiability and/or # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial # SAT algorithm for a circuit class C ${\mathcal C}$ . Say that a symmetric Boolean function f ( x _1,…, x _ n ) is sparse if it outputs 1 on O (1) values of ∑ i x i ${\sum }_{i} x_{i}$ . We show that for every sparse f , and for all “typical” C $\mathcal { C}$ , faster # SAT algorithms for C $\mathcal { C}$ circuits imply lower bounds against the circuit class f ∘ C $f \circ \mathcal { C}$ , which may be stronger than C $\mathcal { C}$ itself. In particular: # SAT algorithms for n ^ k -size C $\mathcal { C}$ -circuits running in 2^ n / n ^ k time (for all k ) imply N E X P does not have ( f ∘ C ) $(f \circ \mathcal { C})$ -circuits of polynomial size. # SAT algorithms for 2 n ε $2^{n^{{\varepsilon }}}$ -size C $\mathcal { C}$ -circuits running in 2 n − n ε $2^{n-n^{{\varepsilon }}}$ time (for some ε > 0) imply Q u a s i - N P does not have ( f ∘ C ) $(f \circ \mathcal { C})$ -circuits of polynomial size. Applying # SAT algorithms from the literature, one immediate corollary of our results is that Q u a s i - N P does not have E M A J ∘ A C C ^0 ∘ T H R circuits of polynomial size, where E M A J is the “exact majority” function, improving previous lower bounds against A C C ^0 [Williams JACM’14] and A C C ^0 ∘ T H R [Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.