Almost-natural proofs

Razborov and Rudich have proved that, under a widely-believed hypothesis about pseudorandom number generators, there do not exist P/poly-computable Boolean function properties with density greater than 2(-poly(n))) that exclude P/poly. This famous result is widely regarded as a serious barrier to proving strong lower bounds in circuit complexity theory, because virtually all Boolean function properties used in existing lower bound proofs have the stated complexity and density. In this paper, we show that under the same pseudorandomness hypothesis, there do exist nearly-linear-time-computable Boolean function properties with only slightly lower density (namely, 2(-q(n)) for a quasi-polynomial function q) that not only exclude P/poly, but even separate NP from P/poly. Indeed, we introduce a simple, explicit property called discrimination that does so. We also prove unconditionally that there exist non-uniformly nearly-linear-time-computable Boolean function properties with this same density that exclude P/poly. Along the way we also note that by slightly strengthening Razborov and Rudich's argument, one can show that their "naturalization barrier" is actually a barrier to proving superquadratic circuit lower bounds, not just P/poly circuit lower bounds. It remains open whether there is a naturalization barrier to proving superlinear circuit lower bounds. (C) 2010 Elsevier Inc. All rights reserved.