= Razborov–Rudich natural-proofs barrier
{c}
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 property of Boolean functions>[constructive], <large property of Boolean functions>[large] and <useful property against a circuit class>[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>.<Natural Proofs by Alexander A. Razborov and Steven Rudich>[section 4]{ref}
Back to article page
