Natural Proofs

@article{citeulike:2800471, abstract = {We introduce the notion ofnaturalproof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in nonmonotone models fall within our definition of natural. We show, based on a hardness assumption, that natural proofs can not prove superpolynomial lower bounds for general circuits. Without the hardness assumption, we are able to show that they can not prove exponential lower bounds (for general circuits) for the discrete logarithm problem. We show that the weaker class ofAC0-natural proofs which is sufficient to prove the parity lower bounds of Furst, Saxe, and Sipser, Yao, and H\r{a}stad is inherently incapable of proving the bounds of Razborov and Smolensky. We give some formal evidence that natural proofs are indeed natural by showing that every formal complexity measure, which can prove superpolynomial lower bounds for a single function, can do so for almost all functions, which is one of the two requirements of a natural proof in our sense.}, author = {Razborov, Alexander A. and Rudich, Steven }, citeulike-article-id = {2800471}, doi = {10.1006/jcss.1997.1494}, journal = {Journal of Computer and System Sciences}, keywords = {complexity}, month = {August}, number = {1}, pages = {24--35}, posted-at = {2008-05-15 02:40:41}, priority = {2}, title = {Natural Proofs}, url = {http://dx.doi.org/10.1006/jcss.1997.1494}, volume = {55}, year = {1997} }

TY - JOUR ID - citeulike:2800471 L3 - citeulike-article-id:2800471 TI - Natural Proofs JF - Journal of Computer and System Sciences VL - 55 IS - 1 SP - 24 EP - 35 N2 - We introduce the notion ofnaturalproof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in nonmonotone models fall within our definition of natural. We show, based on a hardness assumption, that natural proofs can not prove superpolynomial lower bounds for general circuits. Without the hardness assumption, we are able to show that they can not prove exponential lower bounds (for general circuits) for the discrete logarithm problem. We show that the weaker class ofAC0-natural proofs which is sufficient to prove the parity lower bounds of Furst, Saxe, and Sipser, Yao, and Håstad is inherently incapable of proving the bounds of Razborov and Smolensky. We give some formal evidence that natural proofs are indeed natural by showing that every formal complexity measure, which can prove superpolynomial lower bounds for a single function, can do so for almost all functions, which is one of the two requirements of a natural proof in our sense. KW - complexity AU - Razborov, Alexander AU - Rudich, Steven PY - 1997/08// UR - http://dx.doi.org/10.1006/jcss.1997.1494 ER -