...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational complexity >COMPLEXITY OF HARD-CORE SET PROOFS
【24h】

COMPLEXITY OF HARD-CORE SET PROOFS

机译：硬核集协议的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study a fundamental result of Impagliazzo (FOCS'95) known as the hard-core set lemma. Consider any function f : {0,1}~" → {0,1} which is "mildly hard", in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hardcore set lemma says that f must have a hard-core set H of density S on which it is "extremely hard", in the sense that any circuit of size s' = O(s/(_ε1/2 log(_ε1/δ))) must disagree with f on at least (1 - ε)/2 fraction of inputs from H. There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low-level complexity class. We introduce two models of hard-core set proofs, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models. First, we show that using any strongly black-box proof, one can only prove the hardness of a hard-core set for smaller circuits of size at most s' = O(s/_ε1/2 log 1/δ). Next, we show that any weakly black-box proof must be inherently non-uniform-to have a hard-core set for a class G of functions, we need to start from the assumption that f is hard against a non-uniform complexity class with fi(1/ε log |G|) bits of advice. Finally, we show that weakly black-box proofs in general cannot be realized in a low-level complexity class such as AC~0[p]-the assumption that f is hard for AC~0[p] is not sufficient to guarantee the existence of a hard-core set.
机译：我们研究了Impagliazzo（FOCS'95）的基本结果，该结果被称为硬核集引理。考虑任何函数f：{0,1}〜“→{0,1}是“中等难度的”，在某种意义上，任何大小为s的电路在输入的至少一个δ分数上都必须与f不一致。铁杆集引理说，在任何大小为s'= O（s /（_ε1/ 2 log（_ε1/δ）的电路的意义上，f必须具有密度为S的铁芯集H ）））必须在至少来自H的输入的（1-ε）/ 2分数上与f不一致。我们要解决的三个问题是引理：电路尺寸的损失，不均匀性的需要，我们介绍了两种硬核集证明模型，一个是强黑匣子模型，一个是弱黑匣子模型，并证明了在这些模型中这些问题是不可避免的。证明，使用任何强烈的黑匣子证明，只能证明对于最大尺寸为s'= O（s /_ε1/ 2 log 1 /δ）的较小电路的硬核组件的硬度。任何弱黑箱证明都必须天生就不一致-要为函数G的类设置一个硬核集合，我们需要从以下假设开始：假设f对具有fi（1 /εlog | G |）位建议的非均匀复杂性类是困难的。最后，我们证明了弱黑盒证明通常无法在诸如AC〜0 [p]的低级复杂度类别中实现-假设f对于AC〜0 [p]很难满足，不足以保证存在硬核集。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号