NaturalProperty
plain-language theorem explainer
NaturalProperty encodes the Razborov-Rudich notion of a natural property via two propositions: constructivity (polynomial-time computable from truth tables) and largeness (satisfied by random functions with probability at least 1/poly(n)). Complexity theorists bridging recognition operators to classical P vs NP would cite this structure when classifying R-hat certificates on Z³ lattices. The declaration is a direct two-field structure definition with no lemmas or reductions.
Claim. A natural property consists of a constructive predicate (computable in polynomial time from the truth table of a Boolean function) and a largeness predicate (satisfied by a random function with probability at least $1/mathrm{poly}(n)$).
background
The TuringBridge module addresses the remaining gap between RS-native R-hat minimization on J-cost landscapes and classical Turing complexity. It encodes SAT instances as landscapes where R-hat reaches zero defect precisely on satisfiable cases, then shows the resulting certificate fails to be natural. Natural properties, per Razborov-Rudich, must be both constructive and large; the module notes that R-hat operates on full Z³ topology rather than polynomial-size truth tables.
proof idea
This declaration is a direct structure definition introducing the two fields constructive and large. No lemmas are applied; the fields stand as Props whose interpretations are supplied by the module doc-comment and the Razborov-Rudich reference.
why it matters
The structure supplies the precise predicate needed to assert that R-hat certificates are non-natural, completing step 3 of the module's four-step bridge strategy. It feeds the open Turing-simulation question (step 4) and the spectral-gap convergence question (Q3). In the Recognition Science framework it connects the recognition operator and J-cost contractivity to the classical natural-proof barrier, referencing PvsNP_SelfContained_Final.tex.
Switch to Lean above to see the machine-checked source, dependencies, and usage graph.