Natural proofs
- 1 January 1994
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 1 (10) , 204-213
- https://doi.org/10.1145/195058.195134
Abstract
. We introduce the notion of natural proof. We argue that the knownproofs of lower bounds on the complexity of explicit Boolean functions in nonmonotonemodels fall within our definition of natural. We show based on a hardnessassumption that natural proofs can't prove superpolynomial lower boundsfor general circuits. Without the hardness assumption, we are able to show thatthey can't prove exponential lower bounds (for general circuits) applicable to thediscrete logarithm problem. We show...Keywords
This publication has 0 references indexed in Scilit: