= Solution
A property $\mathcal P=(\mathcal P_n)$ of $n$-variable Boolean functions is:
* <constructive property of Boolean functions>[constructive] if membership can be decided from the $2^n$-bit truth table in time polynomial in $2^n$;
* <large property of Boolean functions>[large] if a uniformly random Boolean function belongs to $\mathcal P_n$ with probability at least $2^{-O(n)}$;
* <useful property against a circuit class>[useful] against a circuit class $\mathcal C$ if infinitely often $\mathcal P_n$ contains a function but contains no function computed by circuits in $\mathcal C$ of the target size.
A property satisfying all three conditions is a <natural proof>. The <Razborov–Rudich natural-proofs barrier> states that if exponentially secure <pseudorandom function family>[pseudorandom function families] exist in $\mathrm{P}/\mathrm{poly}$, then no property that is constructive and large is useful against polynomial-size circuits.
Suppose such a property $\mathcal P$ existed. Given oracle access to an unknown $n$-variable function, query its full truth table and run the constructive membership test. This takes $2^{O(n)}$ time. For a truly random function, largeness makes the test accept with probability at least $2^{-O(n)}$. Repetition amplifies this to a constant acceptance probability within $2^{O(n)}$ time.
For a function drawn from the assumed pseudorandom family, each keyed function has polynomial-size circuits, so usefulness makes the test reject for the relevant lengths. The amplified membership test therefore distinguishes the pseudorandom family from a truly random function with constant advantage in exponential time, contradicting exponential pseudorandomness. Hence the three conditions cannot coexist.
Back to article page
