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 models
fall within our definition of natural.
We show based on a hardness assumption
that natural proofs can't prove superpolynomial lower bounds ... more >>>