One way to argue that open problems such as $P\stackrel{?}{=}NP$ are
difficult is to demonstrate that {\em known} methods are inherently too
weak to solve them. This approach was taken in Baker, Gill, and
Solovay \cite{BGS} who used oracle separation results for many major
complexity classes to argue that relativizing proof techniques could
not solve these problems. Since relativizing proof techniques involving
diagonalization and simulation were the only available tools at the
time of their work (1975) progress along known lines was ruled out.
Instead, people started to look at these problems in terms of Boolean
complexity. Along these lines, many (non-relativizing) proof techniques
have been discovered and used to prove lower bounds. These techniques
are highly combinatorial; they exist in a much larger variety than
their recursion-theoretic predecessors. In this talk, we do for the
90's what BGS did for the 70's.
We introduce the notion of a {\em natural} proof. We argue that {\em
all lower bound proofs known to us in non-monotone Boolean complexity
either are natural or can be represented as natural}. We show that if
a cryptographic hardness assumption is true, then {\em no natural proof
can prove superpolynomial lower bounds for general circuits}.
Furthermore, no complexity class containing good pseudo-random function
generators has a natural proof against it. This gives a proof that the
restriction methods which were sufficient to prove the parity lower
bounds of FSS, Ajtai, Yao, and Hastad are inherently incapable of
proving the bounds for $AC^0[q]$-circuits of Razborov and Smolensky.
Razborov has recently found one application of the notion of natural
proof to independence. He has shown that all lower bounds in a certain
fragment of arithmetic naturalize in our sense. Thus, on a hardness
assumption the question of whether SAT has polynomial sized circuits is
independent of this fragment.
(This is joint work with Alexander Razborov.)