TR94-010 Authors: Alexander Razborov, Steven Rudich

Publication: 12th December 1994 00:00

Downloads: 1188

Keywords:

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

Sipser; Yao; and Hastad 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 super-polynomial lower bounds for a single

function,

can do so for almost all functions, which is one of the key requirements to

a natural proof in our sense.