Complexity of Hard-Core Set Proofs
Complexity of Hard-Core Set Proofs
复制标题
硬核集合证明的复杂性
DOI：
10.1007/s00037-011-0003-7
复制
发表时间：
2011
影响因子：
1.4
通讯作者：
H. Wu
中科院分区：
文献类型：
--
作者：
Chi;Shi;H. Wu
我们研究Impagliazzo（FOCS’95）的一个基本结果，即硬核集引理。考虑任何函数$f:\{0,1\}^n\to\{0,1\}$，它是“适度困难”的，即任何规模为$s$的电路在至少$\delta$比例的输入上必须与$f$不一致。那么，硬核集引理表明$f$必须有一个密度为$\delta$的硬核集$H$，在这个集合上它是“极其困难”的，即任何规模为$s' = O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))$的电路在$H$中至少$(1 - \epsilon)/2$比例的输入上必须与$f$不一致。
该引理有三个我们想要解决的问题：电路规模的损失、非均匀性的需求以及它对低层次复杂度类的不适用性。我们引入两种硬核集证明模型，一种是强黑箱模型，一种是弱黑箱模型，并表明在这些模型中这些问题是不可避免的。
首先，我们表明使用任何强黑箱证明，只能证明对于规模至多为$s' = O(s/(\frac{1}{\epsilon^2}\log\frac{1}{\delta}))$的较小电路的硬核集的困难性。接下来，我们表明任何弱黑箱证明必然是内在非均匀的——为了对于一类函数$G$有一个硬核集，我们需要从$f$对具有$\Omega(\frac{1}{\epsilon}\log|G|)$位建议的非均匀复杂度类是困难的这一假设开始。最后，我们表明一般来说弱黑箱证明不能在像$AC0[p]$这样的低层次复杂度类中实现——$f$对$AC0[p]$是困难的这一假设不足以保证硬核集的存在。
We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function $${f:\{0,1\}^n\to\{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 hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size $${s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))}$$ must disagree with f on at least $${(1-\epsilon)/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/(\frac{1}{\epsilon^2}\log\frac{1}{\delta}))}$$ . 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 $${\Omega(\frac{1}{\epsilon}\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 AC0[p]—the assumption that f is hard for AC0[p] is not sufficient to guarantee the existence of a hard-core set.