Natural proof

A natural proof lower bound is based on a property of Boolean functions that is simultaneously constructive, large, and useful against the circuit class being bounded.

A property of $n$-variable Boolean functions is constructive when membership can be decided from a $2^n$-bit truth table in time polynomial in $2^n$.

A property of Boolean functions is large when it contains a nonnegligible fraction, customarily at least $2^{-O(n)}$, of all $n$-variable Boolean functions.

A property is useful against a circuit class when it contains functions at infinitely many input lengths but eventually excludes every function family computed by circuits of the target size in that class.

The Razborov–Rudich natural-proofs barrier says that the existence of sufficiently secure pseudorandom function families rules out constructive, large properties useful against the associated circuit class.