Marginal hitting sets imply super-polynomial lower bounds for permanent
Marginal hitting sets imply super-polynomial lower bounds for permanent
复制标题
边际击球集意味着永久的超多项式下界
DOI：
10.1145/2090236.2090275
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jansen M
中科院分区：
文献类型：
--
作者：
Jansen M
假设是一个一元度=r(N)的多项式，它是由一个大小的算术电路计算的。一元非零次多项式可以在最高点处消失，这是代数的一个基本事实。这意味着，对于检验f是否恒为零，在r+1个点的任意测试集上查询就足够了。这种蛮力方法能改进一点吗？我们建立了一个框架，其中这种边际改进意味着永久不具有多项式大小的算术电路。更正式地，我们对任何特征零域提出如下假设：存在固定深度和某些函数(N)=O(N)，使得对于任意小的ε>；0，存在一个大小至多为2s(n⊂)的命中集合Hn-εZ，其相对于最多2s(nε)的一元次多项式是可以由大小为不变数的算术电路计算的，其中Hn可以由大小为2O(nε)和深度的均匀TC0电路来编码。我们证明了这一假设意味着永久数不具有多项式大小的无常数算术电路。我们的假设为几个重要的复杂性理论猜想提供了统一的视角，因为它是由函数(N)所确定的不同次数范围的猜想引出的。我们将证明它是从一个广为相信的假设引申出来的，即大尺寸布尔回路不能计算Z上0，1-矩阵的恒等式。这个假设也可以很容易地从Shub-Spaleτ猜想[21]中得到，对于任何s(N)，其中s(N)=ω(Logn)和(N)=O(N)。这意味着我们的结果加强了Bürgisser[4]的一个定理，他从τ猜想中得到了相同的下界。对于s(N)=0，假设来源于(n！)我们应用我们的随机性到硬度定理证明了下面的无条件结果：要么永久不具有一致的次指数大小的恒定深度阈值电路，要么永久不具有多项式大小的恒定自由运算电路。转向布尔世界，我们给出了(0，1)-永久的Allender下界[2]的如下加强的简化证明：要么(0，1)-永久不同时在多项式时间和次多项式空间中，要么(0，1)-永久不同时在多项式时间和次多项式空间中同时存在：(0，1)-≠不同时在多项式时间和次多项式空间中，或者对数空间不具有多项式大小的统一恒定深度阈值电路。
Supposefis a univariate polynomial of degreer=r(n) that is computed by a sizenarithmetic circuit. It is a basic fact of algebra that a nonzero univariate polynomial of degreercan vanish on at mostrpoints. This implies that for checking whetherfis identically zero, it suffices to queryfon an arbitrary test set ofr+ 1 points. Could this brute-force method be improved upon by asingle point? We develop a framework where such a marginal improvement implies that Permanent does not have polynomial size arithmetic circuits.More formally, we formulate the following hypothesis for any field of characteristic zero: There is a fixed depthdand some functions(n) =O(n), such that for arbitrarily small ε > 0, there exists a hitting setHn⊂ Z of size at most 2s(nε)against univariate polynomials of degree at most 2s(nε)computable by sizenconstant-free1arithmetic circuits, whereHncan be encoded by uniform TC0circuits of size 2O(nε)and depthd. We prove that the hypothesis implies that Permanent does not have polynomial size constant-free arithmetic circuits.Our hypothesis provides a unifying perspective on several important complexity theoretic conjectures, as it follows from these conjectures for different degree ranges as determined by the functions(n). We will show that it follows fors(n) =nfrom the widely-believed assumption thatpolysize Boolean circuits cannot compute the Permanent of a 0,1-matrix over Z. The hypothesis can also be easily derived from the Shub-Smale τ-conjecture [21], for anys(n) withs(n) = ω(logn) ands(n) =O(n). This implies our result strengthens a theorem by Bürgisser [4], who derives the same lower bound from theτ-conjecture. Fors(n) = 0, the hypothesis follows from the statement that (n!) is ultimately hard, a statement that is known to imply P ≠ NP over C [21].We apply our randomness-to-hardness theorem to prove the following unconditional result for Permanent: either Permanent does not have uniform constant-depth threshold circuits of sub-exponential size, or Permanent does not have polynomial-size constant-free arithmetic circuits.Turning to the Boolean world, we give a simplified proof of the following strengthening of Allender's lower bound [2] for the (0,1)-Permanent: either the (0,1)-Permanent is not simultaneously in polynomial time and sub-polynomial space, or logarithmic space does not have uniform constant-depth threshold circuits of polynomial size.
登录
查看更多内容
DOI：
--
发表时间：
1983
期刊：
JACM
影响因子：
--
作者：
O. Ibarra;S. Moran
通讯作者：
S. Moran
PP 与多项式时间层次结构一样困难
DOI：
--
发表时间：
1991
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Seinosuke Toda
通讯作者：
Seinosuke Toda
随机性与时间：统一假设下的去随机化
DOI：
10.1109/sfcs.1998.743524
发表时间：
1998
期刊：
Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
影响因子：
--
作者：
R. Impagliazzo;A. Wigderson
通讯作者：
A. Wigderson
DOI：
10.1016/s0022-0000(02)00025-9
发表时间：
2002-12
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
W. Hesse;Eric Allender;D. M. Barrington
通讯作者：
W. Hesse;Eric Allender;D. M. Barrington
关于整数的定义和算术电路下界的证明
影响因子：
1.4
作者：
Peter Bürgisser
通讯作者：
Peter Bürgisser