Natural proofs versus derandomization

We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as NEXP ⊄ TC0, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm A is embedded in them), have largeness (A accepts a large fraction of strings), and are useful (A rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are "naturalizing" would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable. Largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove: Constructivity is unavoidable, even for NEXP lower bounds. Informally, we prove for all "typical" non-uniform circuit classes C, NEXP ⊄ C if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by C-circuits. Hence NEXP ⊄ C is equivalent to exhibiting a constructive property useful against C. There are no P-natural properties useful against C if and only if randomized exponential time can be "derandomized" using truth tables of circuits from C as random seeds. Therefore the task of proving there are no P-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results. The two main applications are that NEXP ∩ coNEXP does not have nlog n size ACC circuits, and a mild derandomization result for RP.

我们研究自然证明、去随机化以及证明“弱”电路下界（例如NEXP⊄TC0，这仍然是完全开放的问题）之间的联系。自然证明具有三个性质：它们是构造性的（一个高效算法A嵌入其中），具有广泛性（A接受很大一部分字符串），并且是有用的（A拒绝所有作为小电路真值表的字符串）。“自然化”的强电路下界将与当前的密码学理解相矛盾，然而绝大多数已知的电路下界证明都是自然化的。因此，理解如何寻求非自然证明是至关重要的。一些启发式论证表明构造性应该是可以规避的。广泛性在许多证明技术中是固有的，并且可能是我们目前较弱的技术导致了构造性。我们证明：即使对于NEXP下界，构造性也是不可避免的。非正式地说，我们对于所有“典型的”非均匀电路类C证明，NEXP⊄C当且仅当存在一个多项式时间算法，能将某个函数与所有可由C电路计算的函数区分开来。因此，NEXP⊄C等价于展示一个对C有用的构造性性质。当且仅当使用来自C的电路真值表作为随机种子可以对随机指数时间进行“去随机化”时，不存在对C有用的P - 自然性质。因此，证明不存在P - 自然性质的任务本质上是一个去随机化问题，它比强伪随机函数的存在性弱，但由其隐含。这些特征被应用于产生几个新的结果。两个主要应用是NEXP∩coNEXP不具有nlog n大小的ACC电路，以及一个关于RP的适度去随机化结果。