Hardness amplification within NP

摘要

In this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average? We give a positive answer: if there is a function in NP which is infinitely often balanced and (1−1/poly(n))-hard for circuits of polynomial size, then there is a function in NP which is infinitely often (12+n−1/2+ε)-hard for circuits of polynomial size. Our proof technique is to generalize the Yao XOR Lemma, allowing us to characterize nearly tightly the hardness of a composite function g(f(x1),…,f(xn)) in terms of: (i) the original hardness of f, and (ii) the expected bias of the function g when subjected to random restrictions. The computational result we prove essentially matches an information-theoretic bound.