Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR94-010 | 12th December 1994 00:00

#### Natural Proofs

TR94-010
Authors: Alexander Razborov, Steven Rudich
Publication: 12th December 1994 00:00
Keywords:

Abstract:

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 for
general circuits.
Without the hardness assumption, we are able to show that they can't prove
exponential lower bounds (for general circuits) applicable to the discrete
logarithm problem.
We show that the weaker class of
$AC^0$-natural proofs which is sufficient to prove the parity lower bounds of Furst, Saxe, and