  We study connections between Natural Proofs, derandomization, and the problem
of proving "weak" circuit lower bounds such as ${\sf NEXP} \not\subset {\sf
TC^0}$. Natural Proofs have three properties: they are constructive (an
efficient algorithm $A$ is embedded in them), have largeness ($A$ accepts a
large fraction of strings), and are useful ($A$ rejects all strings which are
truth tables of small circuits). Strong circuit lower bounds that are
"naturalizing" would contradict present cryptographic understanding, yet the
vast majority of known circuit lower bound proofs are naturalizing. So it is
imperative to understand how to pursue un-Natural Proofs. Some heuristic
arguments say constructivity should be circumventable: largeness is inherent in
many proof techniques, and it is probably our presently weak techniques that
yield constructivity. We prove:
  $\bullet$ Constructivity is unavoidable, even for $\sf NEXP$ lower bounds.
Informally, we prove for all "typical" non-uniform circuit classes ${\cal C}$,
${\sf NEXP} \not\subset {\cal C}$ if and only if there is a polynomial-time
algorithm distinguishing some function from all functions computable by ${\cal
C}$-circuits. Hence ${\sf NEXP} \not\subset {\cal C}$ is equivalent to
exhibiting a constructive property useful against ${\cal C}$.
  $\bullet$ There are no $\sf P$-natural properties useful against ${\cal C}$
if and only if randomized exponential time can be "derandomized" using truth
tables of circuits from ${\cal C}$ as random seeds. Therefore the task of
proving there are no $\sf P$-natural properties is inherently a derandomization
problem, weaker than but implied by the existence of strong pseudorandom
functions.
  These characterizations are applied to yield several new results, including
improved ${\sf ACC}^0$ lower bounds and new unconditional derandomizations.
