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 connects lower bounds in circuit complexity with the security of pseudorandom function families. Suppose a property of Boolean functions is constructive, large and useful against a class containing the relevant pseudorandom function family.

Query all $2^n$ inputs of a candidate Boolean function, then run the property's membership test on its truth table. Constructivity makes this take $2^{O(n)}$ time. Largeness gives acceptance probability at least $2^{-O(n)}$ for a uniformly random Boolean function. Usefulness gives rejection for all functions in the chosen small-circuit family at sufficiently large lengths. The property therefore supplies a statistical distinguisher.

A security assumption must cover that running time and distinguishing advantage, at the chosen relation between input length and key length. Security only against polynomial-time algorithms in $n$ does not cover a full truth table test. Razborov and Rudich use a stronger quantitative hardness assumption to obtain the barrier against P/poly. The conclusion restricts a form of lower-bound proof under the assumption; it does not settle whether P equals NP.^[ref]