Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 5

A property $\mathcal{P}=({\mathcal{P}}_n)$ of $n$-variable Boolean functions is:

A property satisfying all three conditions is a natural proof. The Razborov–Rudich natural-proofs barrier states that if exponentially secure 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.

Proceed by structural induction on a Boolean formula $F$. A leaf computes $x_i$ or $\neg x_i$, so its measure is $1$, equal to its leaf count. If the root is an AND gate with subformulae computing $g,h$, thenby property 2; the induction hypothesis bounds this by the sum of the two subformula sizes, which is the size of $F$. Property 3 gives the identical argument for an OR gate. Consequently every formula computing $f$ has size at least $\mu (f)$, so $\mu (f)$ is a formula-size lower bound.