Beyond Natural Proofs: Hardness Magnification and Locality
Beyond Natural Proofs: Hardness Magnification and Locality
复制标题
超越自然证据：硬度放大率和局部性
DOI：
10.1145/3538391
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Chen L
中科院分区：
文献类型：
--
作者：
Chen L
硬度放大减少了主要的复杂性分离(如EXP⊈Nc1)，以针对弱电路模型证明一些自然问题的下界。最近的几部著作[，，，]都建立了这种形式的结果。在最有趣的情况下，对于那些看起来比Q容易得多的问题，所需的下界是已知的，而Q本身也容易受到下界的影响，但这些还不足以证明。在这项工作中，我们提供了更多的这种现象的例子，并研究了使用这种方法证明新的下界的前景。特别是，我们考虑了与硬度放大程序相关的以下基本问题：-硬度放大是否避免了Razborov和Rudich的自然证明障碍？-我们能否采用已知的下界技术来建立Q的所需下界？我们建立了硬度放大的一些实例在以下意义上克服了自然证明障碍：最小电路尺寸问题的某些版本的略微超线性的电路下界意味着自然证明的不存在。由于自然证明的不存在意味着高效学习算法的不存在，我们证明了某些放大定理不仅包含强最坏情况下界，而且排除了有效学习算法的存在。硬性放大可能绕过自然证明，但我们在尝试通过放大来适应现有的下界技术来证明强下界时，找出了一个困难的来源。这一点被局域势垒所捕捉：现有的放大理论无条件地表明，上述问题Q允许使用小的扇入神谕门来扩展高效电路，而针对弱电路模型的下界技术往往很容易扩展到包含这种神谕的电路。这解释了为什么对某些下限的直接适应不太可能通过硬度放大来产生强烈的复杂性分离。
Hardness magnification reduces major complexity separations (such asEXP⊈NC1) to proving lower bounds for some natural problemQagainst weak circuit models. Several recent works [, , , , , , ] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier thanQ, whileQitself is susceptible to lower bounds, but these are not yet sufficient for magnification.In this work, we provide more examples of this phenomenon and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program:–Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich?–Can we adapt known lower-bound techniques to establish the desired lower bound forQ?We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit-size problem imply the non-existence of natural proofs. As the non-existence of natural proofs implies the non-existence of efficient learning algorithms, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms.Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower-bound techniques to prove strong lower bounds via magnification. This is captured by alocality barrier: existing magnification theoremsunconditionallyshow that the problemsQconsidered above admit highly efficient circuits extended with small fan-in oracle gates, while lower-bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.
登录
查看更多内容
给定真值表时最小化析取范式公式和 AC0 电路
DOI：
10.1137/060664537
发表时间：
2008
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Eric Allender;L. Hellerstein;Paul McCabe;T. Pitassi;M. Saks
通讯作者：
M. Saks
DOI：
--
发表时间：
2020
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Valentine Kabanets;Sajin Koroth;Zhenjian Lu;Dimitrios Myrisiotis;I. Oliveira
通讯作者：
I. Oliveira
电路和本地计算
DOI：
--
发表时间：
1989
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
A. Yao
通讯作者：
A. Yao
关于派系的逼近性及相关最大化问题
DOI：
--
发表时间：
2003
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
A. Srinivasan
通讯作者：
A. Srinivasan
放大电路针对多项式时间的下限及其应用
DOI：
--
发表时间：
2013
期刊：
2012 IEEE 27th Conference on Computational Complexity
影响因子：
--
作者：
R. Lipton;Ryan Williams
通讯作者：
Ryan Williams