期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1994
卷号：1994
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We introduce the notion of {\em natural} proof.We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in non-monotone modelsfall within our definition of natural.We show based on a hardness assumptionthat natural proofs can't prove superpolynomial lower bounds forgeneral circuits.Without the hardness assumption, we are able to show that they can't proveexponential lower bounds (for general circuits) applicable to the discretelogarithm problem.We show that the weaker class ofAC0-natural proofs which is sufficient to prove the parity lower bounds of Furst, Saxe, andSipser; Yao; and Hastad isinherently incapable of proving the bounds of Razborov and Smolensky. We give some formalevidence that natural proofs are indeed natural by showing that every formalcomplexity measure which can prove super-polynomial lower bounds for a singlefunction,can do so for almost all functions, which is one of the key requirements toa natural proof in our sense.
关键词：combinatorial properties; lower bounds in non-uniform complexity; Pseudo-Random Generators
