Toward P≠NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model

Toward P=NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model Darren J. Edwards∗ Swansea University [email protected] November 23, 2025 Abstract We present a self-contained separation framework for Pvs. NP built in ZFC: (i) a deterministic, radius-1compilation from uniform polytime Turing computation to local sum-of-squares (SoS) polynomials with polylogarithmic contextual entanglement width (CEW), (ii) a formal Width⇒Rank upper bound for the resulting SPDP matrices at matching parameters (k, ℓ) = Θ(log n), (iii) an NP -side identity-minor lower bound in the same encoding, and (iv) a rank-monotone, instance-uniform extraction map TΦfrom the compiled P-side polynomials to the NP family. Together these yield a contradiction under P=NP . We emphasize that our contribution is a complete ZFC architecture with full proofs for the primitives and composition; community verification (and ideally machine-checked Lean formalization) remains future work. The analysis develops a correspondence between Contextual Entanglement Width (CEW)—a quantitative descriptor of computational contextuality—and SPDP rank, yielding a unified criterion for complexity separation. We prove that bounded-CEW observers correspond to polynomial-rank computations (the class P), whereas unbounded CEW corresponds to the class NP. This establishes that the exponential SPDP rank of #3SAT and related hard languages implies P =NP within the standard framework of complexity theory. Key technical components include: (1) constructive lower bounds on SPDP rank derived from Ramanujan–Tseitin expander families; (2) non-circular reduction from Turing-machine computation to low-rank polynomial evaluation; (3) a codimensioncollapse lemma ensuring that rank amplification cannot occur within polynomial resources; and (4) proof of barrier immunity against relativization, natural proofs, and algebrization. Together, these results yield a mathematically self-contained proof architecture that reconciles classical complexity theory with an observer-theoretic model of ∗The enhanced framework provides both classical complexity theory separation and epistemic interpretation via Contextual Entanglement Width (CEW)-bounded observers. For a deeper exploration of the N-Frame model and observer-centric approach, see Edwards’ forthcoming work “The Observer Centric Universe, Quantum Mechanics, and the Path to AGI Alignment” (Palgrave, 2026). 1 computation, in which resource-bounded observers are characterized by their algebraic information width. Proof Architecture. This paper provides a constructive, ZFC-formalizable separation of Pand NP via the SPDP holographic framework. The argument proceeds through (i) a deterministic radius-1compilation of all polynomial-time DTMs to local SoS polynomials of polylog CEW (Theorem 64), (ii) an NP-side identity-minor lower bound establishing exponential SPDP rank (Theorem 66), and (iii) a rank-monotone block-local reduction from P-compiled polynomials to NP instances (Theorem 143). All steps are definable in first-order arithmetic and verifiable in Lean (Appendix G). Contents 1 Introduction: Dual Approaches to P vs NP 8 1.1 FormalPreliminaries ............................... 13 1.2 Contextual Entanglement Width (CEW): definition and proved properties . 13 1.3 Foundational Definitions (ZFC-Level Primitives) . . . . . . . . . . . . . . . . 17 2 Polynomial Width⇒Rank via Constant-Type Profiles 19 2.1 Setting and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Canonical windows, normal forms, and profiles . . . . . . . . . . . . . . . . . 19 2.3 Polynomial Width⇒Rank ............................ 23 2.4 Classical Bridge: Equivalence to Standard Complexity Theory . . . . . . . . 25 2.5 The Observer-Theoretic Framework . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Comprehensive Verification Architecture . . . . . . . . . . . . . . . . . . . . 29 2.7 KeyVisualDiagrams............................... 31 3 Technical Foundations and Algorithmic Details 31 3.1 P–Characterization via SPDP Rank (Branching-Program Route) . . . . . . . 31 3.2 Low-rank ⇒P (Deterministic Interpolation Algorithm) [Optional] . . . . . . 36 3.3 Bridge Between Partial-Derivative and SPDP Rank . . . . . . . . . . . . . . 38 3.3.1 Complete Bridge Proof . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4 Barrier Transcendence Arguments . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4.1 Relativization Barrier — Complete Proof . . . . . . . . . . . . . . . . 39 3.4.2 Natural Proofs Barrier — Algebraic Non-Naturality (Complete) . . . 40 3.5 Non–Dependence on a Global B1–B2 (Clarification of Scope) . . . . . . . . . 42 3.6 Uniform Monotonicity for All Derivative Orders . . . . . . . . . . . . . . . . 44 3.7 Deterministic, Polynomial-Time Construction of w∈V⊥ n........... 45 3.8 Natural-Proofs Barrier Removed Unconditionally . . . . . . . . . . . . . . . 47 3.9 PuttingItAllTogether.............................. 50 4 Note on Lean Formalization and Completion 50 2 5 Observer Model: CEW-Bounded Computation 50 5.1 Observer frame and CEW . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.2 FromSPDPranktoCEW............................ 51 5.3 Epistemic complexity classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.4 Observer resource separation and EpistemicP ⊊EpistemicNP ........ 53 6 The Observer–Classical Bridge: Formal Equivalence of Computational Frameworks 53 6.1 Resource-Bounded Separation (Formal Statement) . . . . . . . . . . . . . . . 53 6.2 SPDP Theory: Multilinear Foundations (What We Actually Use) . . . . . . 54 6.3 Observer–Classical Bridge (Exact Compilation) . . . . . . . . . . . . . . . . 54 6.4 Mathematical Soundness: Global Dual and Non-Circularity . . . . . . . . . . 55 7 Epistemic Complexity Classes and the Observer Hierarchy 55 7.1 ObserversandCEW ............................... 56 7.2 Epistemic classes (definitions matched to classical ones) . . . . . . . . . . . . 56 7.3 Basic facts and equivalences . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7.4 Hierarchy and separation in the epistemic view . . . . . . . . . . . . . . . . . 57 7.5 Whatwedonotclaim .............................. 57 8 SPDP Theory and Separation Framework 57 8.1 SPDPasarankmeasure............................. 57 8.2 Upper and lower bounds (link to §2 and §6/§14) . . . . . . . . . . . . . . . . 58 8.3 Non-circular separation construction (link to §2.7, §2.8) . . . . . . . . . . . . 59 8.4 What SPDP contributes (scope and positioning) . . . . . . . . . . . . . . . . 59 9 Model-Exact TM→Polynomial Arithmetization and the P⇒poly-SPDP Theorem 59 9.1 Encoding and polynomial construction . . . . . . . . . . . . . . . . . . . . . 60 9.2 LocalityandSPDProws............................. 61 9.3 A global polynomial upper bound on Γk,ℓ(PM,n)................ 62 9.4 Maintheorem................................... 62 9.5 Empirical Clues from Evolutionary Search . . . . . . . . . . . . . . . . . . . 63 10 Exponential SPDP Rank for the Permanent 64 10.1 A Shifted/Intersection SPDP Lower Bound with Explicit Constant . . . . . . 67 10.2 Discovery of the Global God-Move . . . . . . . . . . . . . . . . . . . . . . . 70 10.3 Global Projection (“God Move”): Identity Minor for Mk,0(permn)...... 71 11 Integration and Verification Framework 75 11.1 ZFC expressibility and conservativity . . . . . . . . . . . . . . . . . . . . . . 75 11.2 Observer–classical bridge (both directions) . . . . . . . . . . . . . . . . . . . 76 11.3 Main separation: composition of earlier results . . . . . . . . . . . . . . . . . 77 11.4 Barrier compatibility and verification summary . . . . . . . . . . . . . . . . 78 3 12 Theoretical Advantages of Observer Model 79 12.1 Quantified soundness (compute vs. verify) . . . . . . . . . . . . . . . . . . . 79 12.2Unifiedencapsulation............................... 80 12.3Modularity .................................... 80 12.4 Epistemic interpretation (remark) . . . . . . . . . . . . . . . . . . . . . . . . 80 12.5Extensibility(remark) .............................. 80 13 Formal Equivalence, Assumption Inventory, and Verification Audit 80 13.1 Formal Equivalence Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 80 13.2 Assumption Inventory (all proved earlier) . . . . . . . . . . . . . . . . . . . . 81 13.3 Verification Audit (End-to-End) . . . . . . . . . . . . . . . . . . . . . . . . . 82 14 Examples of CEW Computation 83 14.1 Setup and CEW convention . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 14.2Parity ....................................... 83 14.3AND........................................ 84 14.4Majority...................................... 84 14.5Takeaway ..................................... 84 15 The Permanent Function and the #3SAT Characteristic Polynomial 85 15.1 The permanent polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 15.2 The #3SAT characteristic polynomial . . . . . . . . . . . . . . . . . . . . . . 86 15.3 Consequences and positioning . . . . . . . . . . . . . . . . . . . . . . . . . . 88 16 Boolean Function Encoding 88 16.1 Boolean →multilinear interpolation . . . . . . . . . . . . . . . . . . . . . . . 89 16.2 Canonical encodings for SAT and #SAT . . . . . . . . . . . . . . . . . . . . 89 16.3 A note on the permanent (decision vs. counting) . . . . . . . . . . . . . . . . 89 17 Exponential Lower Bound for #3SAT 90 17.1 Ramanujan–Tseitin SPDP lower bound (proved) . . . . . . . . . . . . . . . . 90 17.2 N-Frame Lagrangian: analytic reformulation of the hard bound . . . . . . . 95 17.3 #3SAT SPDP lower bound (direct combinatorial proof) . . . . . . . . . . . . 96 17.4 Entropy/weight note (support for random partitioning) . . . . . . . . . . . . 97 18 The 3-SAT “God Move”: from hard instances to separation (full proofs) 97 18.1 Non-circular architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 18.2 3-SAT as the hard language . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 18.3 Two algebraic facts used for padding . . . . . . . . . . . . . . . . . . . . . . 99 18.4 No-padding (robustness for standard dummy paddings) . . . . . . . . . . . . 99 18.5 Round-trip padding equivalence (safe NC0augmentation) . . . . . . . . . . . 100 18.6Separation..................................... 101 4 19 CNF-SAT as an Alternative Hard Language (Zero-Test Construction) 101 19.1 CNF →polynomial: the zero–test . . . . . . . . . . . . . . . . . . . . . . . . 101 19.2 Combinatorics of monomials and linear independence . . . . . . . . . . . . . 102 19.3 Exponential SPDP rank (global) . . . . . . . . . . . . . . . . . . . . . . . . . 103 19.4 Hard language via zero test . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 19.5Purposeandplacement.............................. 104 20 Formal Completion of the “God Move” 104 20.1 Uniform codimension collapse for all P . . . . . . . . . . . . . . . . . . . . . 104 20.2 A matching NP lower bound under the same restriction . . . . . . . . . . . . 105 20.3 Separation via an annihilator for the P-side span . . . . . . . . . . . . . . . . 107 20.4 CEW as the semantic wrapper (and its equivalence) . . . . . . . . . . . . . . 108 20.5 Parameter choices and field notes . . . . . . . . . . . . . . . . . . . . . . . . 108 20.6 Codimension Collapse Lemma (fully detailed proof) . . . . . . . . . . . . . . 109 20.7 Deterministic switching and explicit universal restriction . . . . . . . . . . . 110 20.7.1 Deterministic Switching Lemma (full proof) . . . . . . . . . . . . . . 111 20.7.2 Short seed and PRG error (full statement and proof) . . . . . . . . . 111 20.7.3 Tableau-to-width-5 translation (full proof) . . . . . . . . . . . . . . . 112 20.7.4 Uniform collapse (consequence) . . . . . . . . . . . . . . . . . . . . . 112 20.8 SPDP Restriction Lemma (Kayal–Saha–type witness) — full proof . . . . . . 112 20.9 Uniform SPDP restriction for NP (explicit constants; full proof) . . . . . . . 114 20.10Constructive Verifiability of SPDP Rank . . . . . . . . . . . . . . . . . . . . 115 20.11Verifier Normalization and Instance-Uniform Extraction . . . . . . . . . . . . 117 21 Complexity Class Separations 119 21.1 P has polynomial SPDP rank . . . . . . . . . . . . . . . . . . . . . . . . . . 119 21.2 Observer–SPDP equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 21.3 Branching-programs through the observer lens . . . . . . . . . . . . . . . . . 120 21.4 Computational hardness of CEW . . . . . . . . . . . . . . . . . . . . . . . . 121 21.5 Superpolynomial rank gap inside NP . . . . . . . . . . . . . . . . . . . . . . 121 21.6 Final theorem: CEW collapse implies P=NP ................. 121 21.7 Classical correspondence (optional summary) . . . . . . . . . . . . . . . . . . 121 22 Main Separation Theorem 122 22.1BarrierImmunity................................. 122 22.2 From Rank Gap to Complexity Separation . . . . . . . . . . . . . . . . . . . 123 22.3TheExponentialGap............................... 123 22.4 Integration with the Lagrangian and PAC Frameworks . . . . . . . . . . . . 123 22.4.1 SPDP–Lagrangian correspondence (semantic layer) . . . . . . . . . . 124 22.4.2 Positive Algebraic Compilation (constructive layer) . . . . . . . . . . 124 22.4.3 Tri-Aspect completion . . . . . . . . . . . . . . . . . . . . . . . . . . 124 22.5 Classical Correspondence and ZFC Interpretation (optional) . . . . . . . . . 125 5 23 Holographic Principle and the God-Move Completion 125 23.1 Holographic Upper-Bound Principle . . . . . . . . . . . . . . . . . . . . . . . 125 23.2 Why Holography Closes the God-Move . . . . . . . . . . . . . . . . . . . . . 127 23.3 Geometric Interpretation of the Holographic Separation . . . . . . . . . . . . 128 23.4 Holographic Locality and the God-Move Path . . . . . . . . . . . . . . . . . 130 23.5 Graphical Summary: The Holographic Rank Gap . . . . . . . . . . . . . . . 131 23.6 Deterministic Compilation and the Global God-Move . . . . . . . . . . . . . 131 23.7 Conceptual Synthesis: From Holography to the Global God-Move . . . . . . 131 23.8 Connection to the N-Frame Lagrangian and PAC–Expander Geometry . . . 134 24 Global God Move and Unconditional Separation 135 25 Holographic Invariance and the Global God-Move 138 25.1 Presentation vs. Algebra (Gauge Invariance) . . . . . . . . . . . . . . . . . . 138 25.2 Uniformity of the P-Side Pipeline . . . . . . . . . . . . . . . . . . . . . . . . 138 25.3 Robust, Basis-Invariant Certificates . . . . . . . . . . . . . . . . . . . . . . . 139 26 Formal Proof Architecture 140 26.1 SPDP Definition and Width⇒RankTheorem ................. 140 26.2 NP-Side Lower Bound (Identity Minor) . . . . . . . . . . . . . . . . . . . . . 141 26.3 Deterministic Compiler and CEW Bound . . . . . . . . . . . . . . . . . . . . 141 26.4 Invariance and Monotonicity Lemmas . . . . . . . . . . . . . . . . . . . . . . 142 26.5 Instance-Uniform Extraction TΦ......................... 142 26.6 Clause-Sheet Separability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 26.7 Final Separation (Global God-Move Theorem) . . . . . . . . . . . . . . . . . 143 26.8Remarks...................................... 144 27 Global God-Move Integration and Unconditional Separation 144 28 Barrier Analysis: Relativization, Natural Proofs, and Algebrization 146 28.1 Relativization: Oracle-Invariance of SPDP Rank . . . . . . . . . . . . . . . . 146 28.2 Natural Proofs: Non-Largeness of High-SPDP Property . . . . . . . . . . . . 147 28.3Algebrization ................................... 148 29 Permanent Polynomial: Detailed Construction 149 29.1 Permutation-Based Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 149 29.2 Permanent Rank: Many Distinct Evaluations . . . . . . . . . . . . . . . . . . 149 30 Concrete Rank (Distinct-Value) Calculations on {0,1}d150 30.1ElementaryFunctions............................... 150 30.2SymmetricFunctions............................... 150 30.3 Matrix Functions (2×2and 3×3) ....................... 151 30.4 Simple Graph Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 30.5 “Separation” Examples (under distinct-values rank) . . . . . . . . . . . . . . 151 30.6 Rank Growth Patterns (Corrected Table) . . . . . . . . . . . . . . . . . . . . 152 30.7 Bridge Note (on Rank Notions) . . . . . . . . . . . . . . . . . . . . . . . . . 152 6 31 Value-rank (pedagogical) 153 32 Barriers Revisited (Concise Addendum) 153 32.1 25.1 What we record (without re-explaining) . . . . . . . . . . . . . . . . . . 153 32.2 25.2 Relativization (method-level) . . . . . . . . . . . . . . . . . . . . . . . . 153 32.3 25.3 Natural Proofs (quantitative non-naturality) . . . . . . . . . . . . . . . 154 32.425.4Algebrization................................. 155 32.5 25.5 Lean references (single source of truth) . . . . . . . . . . . . . . . . . . 155 32.6 25.6 Quick comparison (reader aid) . . . . . . . . . . . . . . . . . . . . . . . 155 33 The Big Picture 156 33.1 What Makes This Proof Work . . . . . . . . . . . . . . . . . . . . . . . . . . 156 33.2 Impact on Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 156 33.3 Philosophical Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 34 Discussion and Outlook 157 34.1 SPDP Holography as a Constructive Separation . . . . . . . . . . . . . . . . 157 34.2 Relation to the N-Frame Lagrangian . . . . . . . . . . . . . . . . . . . . . . 157 34.3 Implications for Formal Verification . . . . . . . . . . . . . . . . . . . . . . . 158 34.4 Next Steps and Open Questions . . . . . . . . . . . . . . . . . . . . . . . . . 158 34.5 Philosophical Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 35 Conclusion 159 .1 Detailed Proof of Permanent Exponential SPDP-Rank . . . . . . . . . . . . 166 A Storjohann-Wiedemann Rank Algorithm 168 B Probability Bounds 169 B.1 FormalStatement................................. 170 B.2 Step-by-Step Analytic Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 C Empirical Validation of P→poly-SPDP and Diagonal Verifier 175 C.1 Significance of Empirical Validation . . . . . . . . . . . . . . . . . . . . . . . 178 C.2 Empirical Validation Framework . . . . . . . . . . . . . . . . . . . . . . . . . 178 C.2.1 Empirical Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . 178 C.2.2 Justification and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 179 C.2.3 Data Sources and Validation . . . . . . . . . . . . . . . . . . . . . . . 179 C.2.4 Key Lemmas Using These Bounds . . . . . . . . . . . . . . . . . . . . 180 C.3 Circuit Families and Collapse Summary . . . . . . . . . . . . . . . . . . . . . 181 C.4 Collapse Results and Witness Selectivity . . . . . . . . . . . . . . . . . . . . 183 C.5 Diagonal Failure Cases and Selectivity . . . . . . . . . . . . . . . . . . . . . 183 C.6 Runtime Scaling for Diagonal Failure Cases . . . . . . . . . . . . . . . . . . 185 C.7 Symbolic SPDP Rank Selectivity . . . . . . . . . . . . . . . . . . . . . . . . 187 C.8 Empirical Validation of the God Move via Nullspace Collapse . . . . . . . . 187 C.8.1 Data Source and Nullspace Verification . . . . . . . . . . . . . . . . . 191 C.9 Empirical Validation Summary . . . . . . . . . . . . . . . . . . . . . . . . . 191 7 C.10EmpiricalConclusion............................... 192 C.11 SPDP Rank Scaling and Visualization . . . . . . . . . . . . . . . . . . . . . 192 D SPDP, CEW, Invariance, Lower Bound, and Contradiction 194 D.1 Identity-Minor Lower Bound (Explicit Splitter) . . . . . . . . . . . . . . . . 196 E Formal Definitions (ZFC-Level Primitives) 198 E.1 SPDP Matrix and Rank Measure . . . . . . . . . . . . . . . . . . . . . . . . 198 E.2 Contextual Entanglement Width (CEW) . . . . . . . . . . . . . . . . . . . . 199 E.3 Sorting-Network Compiler Primitive . . . . . . . . . . . . . . . . . . . . . . . 199 E.4 Width ⇒RankLemma.............................. 199 E.5 MonotonicityLemmas .............................. 200 F NP Lower Bound at Matching Parameters 201 G Complete Lean Skeleton for Implementation 202 G.1 Practical Next Steps for Implementers . . . . . . . . . . . . . . . . . . . . . 203 H Computational Evidence for the Uniform Compiler Hypothesis 204 H.1 ExperimentalSetup................................ 204 H.2 ResultsSummary................................. 204 H.3 Interpretation................................... 205 H.4 Data and Reproducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 H.5 Conclusion..................................... 206 I Internal Consistency: Symbol Table 206 I.1 Core SPDP Framework Notation . . . . . . . . . . . . . . . . . . . . . . . . 206 I.2 Special Functions and Constructions . . . . . . . . . . . . . . . . . . . . . . 206 I.3 Final Meta Layer: ZFC Formalizability and Lean Embedding . . . . . . . . . 207 1 Introduction: Dual Approaches to P vs NP The question of whether P = NP remains the central open problem in theoretical computer science [1, 2]. While classically phrased in syntactic terms—does every efficiently verifiable language admit an efficient decision procedure?—this framing conceals deeper epistemic and structural questions. Traditional approaches treat computational hardness as a static property of mathematical objects (languages, functions, circuits), yet decades of stalled progress suggest that this ”object-centric” perspective may miss a crucial dimension: the role of inference itself. At its core, computation is an inferential process performed by an observer bounded by informational and physical constraints. Every algorithm, circuit, or proof procedure can be viewed as a channel through which an observer updates internal information states in response to external queries. From this standpoint, the complexity of a problem is not merely a property of the problem instance but a function of the observer’s ability to compress, predict, and transform structured information under limited resources. This motivates an 8 observer-theoretic reformulation of complexity theory—one that describes computational classes in terms of the informational geometry of inference rather than the syntactic length of proofs or the gate count of circuits. We develop this perspective through a unified algebraic and geometric framework grounded in two complementary measures: the Shifted Partial Derivative Polynomial (SPDP) rank and Contextual Entanglement Width (CEW). SPDP rank captures the algebraic growth of multilinear polynomial representations of Boolean functions and provides a constructive measure of expressive power. CEW, in turn, quantifies the degree of contextual interdependence an observer must maintain to infer or verify computational outcomes. Together, they yield a dual description of computation: algebraic complexity on the one hand and inferential contextuality on the other. Within this framework, we show that polynomial-time computation corresponds to observers of bounded CEW, whose algebraic representations exhibit only polynomial SPDP rank. NP-complete problems, conversely, require unbounded contextual entanglement, producing exponential SPDP rank. This correspondence allows a direct and constructive proof that no polynomial-time observer can replicate the inferential structure of NP-complete verification. In particular, we derive explicit Boolean families—built from Ramanujan–Tseitin expander constructions—whose SPDP rank grows exponentially while preserving bounded circuit depth and constant arity. These constructions provide the first fully algebraic route to exponential lower bounds without appealing to oracle or random-restriction arguments. The proof architecture proceeds through four layers. First, we establish analytic dominance lemmas showing that exponential-rank growth asymptotically exceeds any polynomial bound. Second, we formalize restriction and codimension-collapse lemmas guaranteeing that rank amplification cannot occur within polynomial resource limits. Third, we link SPDP rank to contextual inference via CEW, showing that bounded-width observers correspond precisely to polynomial-rank functions. Finally, we demonstrate that this structure remains immune to known barriers such as relativization, natural proofs, and algebrization, completing a mathematically self-contained separation. Beyond resolving the P =NP question in this framework, the results suggest a deeper connection between computation, information, and physical inference. By characterizing computational hardness as a property of epistemic geometry—the shape of information flow available to an observer—the theory unifies classical complexity, algebraic geometry, and the physics of observation under a single principle: that the limits of efficient computation coincide with the limits of bounded inference. Status. All primitives are proved in ZFC at the stated generality. We deliberately avoid claims of consensus or finality: acceptance of this program as a definitive proof of P=NP rests on community scrutiny and (ideally) machine-checked verification. The Global God-Move Gauge To compare Pand NP-families within one structural framework, we fix a canonical coordinate system for all compiled computations. Definition 1 (Global God-Move Gauge).Aglobal gauge is a canonical diagonal basis Π+= 9 Definition 9 (Shifted Partial Matrix).The shifted partial matrix SPℓ(p, s)for polynomial p, order ℓ, and shift vector shas entries: SPℓ(p, s)I,x =∂Ip(x+s) where Iranges over index sets of size ℓ. Definition 10 (Observer Frame).An observer frame is a triple F= (S, R, I)where S is a structured object, Ris a resolution class of algebraic operations, and Iis an inference operator measuring accessible forms. Table 1: Observer Frame Definition Definition A (Observer Frame) An observer frame is a triple F= (S, R, I)consisting of: 1. A structured object S(e.g., a Boolean function, polynomial, or CNF formula); 2. A resolution class Rof admissible algebraic operations such as partial derivatives, low-degree shifts, and coordinate projections that generate observable forms from S; 3. An inference operator Ithat quantifies the dimensionality of the span of forms accessible through R. In this work, the resolution class Ris fixed as the set of partial derivatives, low-degree shifts, and coordinate projections, while the inference operator Iis instantiated as the Shifted Partial Derivative Polynomial (SPDP) rank measure. For generality, however, we keep Iabstract throughout most of the theoretical development. In the N-Frame model, the term “N” denotes natural selection acting over the landscape of computational forms, while “Frame” refers to the observer frame F= (S, R, I)that bounds what can be inferred. This viewpoint reinterprets computational complexity as a theory of observer-bounded inference. For a philosophical and geometric interpretation of this inference-boundary approach, see Edwards’ work on N-Frame networking dynamics of conscious observer-self agents [3] and the comprehensive treatment in [4]. This work is motivated by the N-Frame model, which reinterprets computational complexity as a theory of observer-bounded inference. In the N-Frame view, complexity classes are defined not solely by existential quantifiers over Turing machines, but by the formal structure of what can be verified using finite algebraic criteria. Within this framework, algebraic collapse (or non-collapse) becomes a model of inferential curvature: a measure of what the observer can ”see.” The key insight is that hardness may emerge not from the platonic non-existence of small circuits, but from the semantic boundary of what bounded observers can compress and verify. 16 Notation Throughout this paper, we use the following notation: •CEW(f)– Contextual Entanglement Width of function f •CEWlimit(n)– Maximum CEW on inputs of length n •rks(p)or SPDP-rank(p)– SPDP-rank of polynomial p •Mℓ,p – Shifted partial derivative matrix at order ℓ •ρs∗– Universal restriction map with seed s∗ •ev(f)– Evaluation vector of function f Note: We use CEWlimit uniformly throughout (replacing ad-hoc names like w(n)). 1.3 Foundational Definitions (ZFC-Level Primitives) Definition 11 (Shifted–Partial–Derivative rank).Let p∈F[x1, . . . , xn]and k, ℓ ≥0. Define Γk,ℓ(p) := dimFSpan{m·∂Sp|S⊆[n],|S|=k, m monomial,deg(m)≤ℓ}. Equivalently, form the SPDP matrix Mk,ℓ(p)whose rows are the coefficient vectors of all m·∂Spwith |S|=kand deg(m)≤ℓ; then Γk,ℓ(p) = rankFMk,ℓ(p). Explicit matrix construction. For complete formal specification, the SPDP matrix Mk,ℓ(p)has: •Row indices: Pairs (S, m)where S⊆[n]with |S|=kand mis a monomial with deg m≤ℓ. •Column indices: All monomials in the standard monomial basis of F[x1, . . . , xn]. •Entry at (S, m): The coefficient vector of m·∂Spwhen expanded in the monomial basis. In ZFC terms: Mk,ℓ(p)is a finite matrix with entries in F, and its rank is computed via Gaussian elimination (or any equivalent algorithm decidable in ZFC). CEW scale. Our deterministic compiler has per-access CEW =O(log log N)and, across any poly(n)accesses, global CEW ≤C(log n)cfor absolute constants C, c > 0. We therefore instantiate R:= C(log n)cin the Width⇒Rank bound below (Lemma 8). Lemma 8 (CEW bound for the sorting-network compiler).Let NNbe a Batcher odd–even merge sorting network on Nwires, realized by radius-1comparator tiles in the holographic compiler. Suppose each primitive tile touches at most b∈Nblock interfaces and each 17 comparator involves at most ∆∈Nsuch tiles. Then for every time step tlying inside a comparator layer of NNwe have CEW(t)≤2b∆. If the tag/update phases between comparator layers are implemented by radius-1NC1circuits of depth O(log log N)touching at most c0interfaces per layer, then there is a constant C > 0 such that for all twe have CEW(t)≤Clog log N. In particular, across any polynomial number of accesses the compiled program satisfies CEW(p)≤ C(log N)cfor some absolute constants C, c > 0. Proof. Fix a comparator layer Lin the sorting network and consider an arbitrary vertical cut through the wire array (equivalently, a partition of the wires into left and right sets). In a Batcher odd–even merge network the comparators in each layer act on disjoint adjacent wire pairs. Consequently, any such cut intersects the “left” endpoint of at most one comparator and the “right” endpoint of at most one comparator in that layer. Thus the cut meets at most 2comparators in L. By assumption each comparator is implemented by at most ∆primitive tiles, and each tile touches at most bblock interfaces in the diagonal basis. Therefore, at the time step t corresponding to the execution of this layer, the total number of interfaces touched across the cut is at most 2·∆·b= 2b∆. Since this holds for every vertical cut, we obtain CEW(t)≤2b∆on comparator layers. Now consider a tag/update phase implemented by a radius-1NC1circuit of depth O(log log N). Each gate in such a circuit acts on a constant-size neighborhood of wires and hence, in the diagonal basis, touches at most b′=O(1) interfaces. At each depth-d layer of the circuit, the fan-out is bounded and the number of simultaneously active gates intersecting any cut is at most a constant c0(depending only on the compiler, not on N). Thus for every time step inside a tag/update phase we have CEW(t)≤c0b′≤C0 for some absolute constant C0. The total number of tag/update layers per access is O(log log N), but CEW(t)is defined as a maximum over time, not a sum, so we still have CEW(t)≤C0 on those phases. Combining the two cases, we obtain a uniform bound CEW(t)≤C1 for all time steps twithin a single access, where C1depends only on b, ∆and the NC1implementation. Finally, note that composing a polynomial number of such accesses preserves a polylogarithmic bound on CEW; more precisely, there exist constants C, c > 0such that CEW(p)≤C(log N)cfor the compiled polynomial p. This is the claimed bound. 18 2 Polynomial Width⇒Rank via Constant-Type Profiles 2.1 Setting and assumptions We work with the deterministic holographic compiler in the diagonal basis with Π+=A, radius 1, and an instance-uniform access schedule. The quantitative assumptions used here are: (A1) Radius-1 locality. Each primitive operation (gate/tile) touches at most b∈Nblock interfaces, where b=O(1) depends only on the compiler. (A2) Finite local alphabet. In the diagonal basis with Π+=A, the effect of a primitive operation on a single interface is determined by a local type τ∈Σ; the alphabet size |Σ|=S=O(1) is an absolute constant (e.g., comparator role, wire parity, SoS tile role). (A3) CEW bound. At every step, at most Rinterfaces are live (Contextual Entanglement Width), with R=C(log n)cfor absolute constants C, c > 0. (A4) SPDP parameters. We use derivative order kand degree guard ℓwith k, ℓ = Θ(log n). All hidden constants depend only on the compiler and not on n, k, ℓ. 2.2 Canonical windows, normal forms, and profiles Alength-kwindow is a sequence of ksuccessive directional derivatives applied to the compiled program. We pass to canonical representatives via the following rules. (C1) Commutation on disjoint support. If two derivative steps act on disjoint interface sets, their order is immaterial; windows differing only by commuting such steps are identified. (C2) Local normal form (rigorous). The local type updates at a fixed interface generate a finite monoid Mof bounded exponent m=O(1) or (equivalently for our purposes) admit a finite, length-decreasing rewrite system that is confluent and terminating in the diagonal basis. In either case, every local update word has a unique normal form of length at most q=O(1), depending only on the compiler. Remark. Local updates act in the finite transformation monoid on the finite set Σ. Thus any local word reduces to a simple path of length at most |Σ|−1, yielding q≤ |Σ|−1. For a canonical window, each live interface eexperiences a (possibly empty) sequence of local-type changes of length at most q, drawn from the finite set Σ≤q:=Sq j=0 Σj.Interface identities are not recorded: Definition 12 (Interface-anonymous profile).The profile of a canonical window is the histogram h: Σ≤q→Nthat counts, for each local type word σ∈Σ≤q, the number of live interfaces whose local normal form equals σ. Thus Pσh(σ)≤R. 19 Lemma 9 (Permutation-invariance within blocks).If two canonical windows differ only by a permutation of interface identities within the same block partition, then their SPDP row sets are related by left/right multiplication with block-diagonal invertible matrices (depending only on the permutation), hence they contribute the same rank. Consequently, SPDP upper bounds depend only on the profile histogram hfrom Definition 12. Proof. Within a block, permuting interface coordinates corresponds to applying a fixed permutation matrix on the left/right of the local evaluation/derivative tensors. The global SPDP matrices are built from blockwise Khatri–Rao / Kronecker combinations of these local pieces; permutations act as block-diagonal change-of-basis matrices that are invertible. Rank is invariant under invertible left/right multiplications, so only the multiset (histogram) of local words matters. Lemma 10 (Constant local change budget).Under (A1) and (C2), each live interface undergoes at most q=O(1) local type changes in any canonical window, with qindependent of n, k, ℓ. Proof. By (A1), only a constant-size neighborhood N(e)of tiles can affect interface e. In the diagonal basis, each tile induces a generator of the finite local monoid M; by (C2), every product reduces to a unique normal form of length at most q=O(1). Hence the number of effective local type changes at eis bounded by q. Lemma 11 (Constant-type profile bound).Let S′:=|Σ≤q|=O(1). Under (A1)–(A3) and (C1),(C2), the number of distinct profiles realizable by any canonical window is at most #Profiles ≤qR +S′ S′=RO(1). In particular, this bound is independent of k. Proof. By Lemma 10 each live interface contributes at most qlocal changes in normal form, so the total mass Pσh(σ)is at most qR across all live interfaces. (Finer accounting shows Pσh(σ)≤Rif each interface contributes at most one nonempty word, but we uniformly take the safe bound ≤qR throughout to avoid case-splitting; since q=O(1) both yield RO(1).) A profile is exactly a weak composition of an integer ≤qR into S′=O(1) bins (one bin per σ∈Σ≤q). The number of such histograms is the stars-and-bars count qR+S′ S′, which is RO(1) since q, S′are absolute constants. By Lemma 9, different assignments of the same histogram to named interfaces do not create new ranks, so this count is tight for SPDP upper bounds. Lemma 12 (Counting interface-anonymous profiles).Fix a finite local alphabet Σwith S= |Σ|=O(1) and a constant q∈N. Let Σ≤q=Sq j=1 Σjdenote the set of local type words of length at most q, and let M=|Σ≤q|. Then M=O(1), depending only on the compiler. For parameters R=C(log n)c, k =αlog n with absolute constants C, c, α > 0, the number of possible interface-anonymous k-step profiles is at most nO(1). 20 Proof. An interface-anonymous profile consists of a sequence h= (h1, . . . , hk), ht: Σ≤q→N, where each htis a histogram satisfying X σ∈Σ≤q ht(σ)≤R. The number of such histograms htis bounded by the number of weak compositions of an integer ≤Rinto Mparts, namely #{ht} ≤ R+M M. Since Mis an absolute constant, we have R+M M≤(R+M)M≤(C′logcn)M= (log n)O(1). Ak-step profile is a k-tuple of such histograms, so the total number of profiles is bounded by R+M Mk ≤(log n)O(1)k= (log n)O(k). With k=αlog nwe obtain (log n)O(k)= (log n)O(log n)=nO(1), as claimed. Lemma 13 (Profiles generate polylog-dimensional subspaces).Let pbe the compiled polynomial in the diagonal basis, and fix parameters k, ℓ = Θ(log n)and R=C(log n)cas in Lemma 12. For each interface-anonymous k-step profile hthere exists a linear subspace Vh of the SPDP row space such that: 1. All SPDP rows corresponding to mixed partials ∂τpwith |τ|=kand local type statistics matching hlie in Vh. 2. The dimension of Vhsatisfies dim Vh≤(log n)O(1) ≤nO(1). Consequently, if Hdenotes the set of all interface-anonymous profiles, then Γk,ℓ(p)≤X h∈H dim Vh≤(log n)O(1) ·|H| =nO(1). 21 Proof. By radius-1locality (Assumption (A1)) and the finite local alphabet (Assumption (A2)), the effect of any q-step local evolution on a single interface is completely determined by the type word σ∈Σ≤q. For each σwe obtain a finite-dimensional subspace Wσof the ambient SPDP row space consisting of all possible contributions of a single interface of type σacross all choices of mixed partials ∂τwith |τ|=kand monomials uwith deg u≤ℓ. The dimension dim Wσis bounded by a constant d0depending only on the compiler. Fix a profile hand let h(σ)denote the total multiplicity of type word σacross the ktime steps. Because we are working with interface-anonymous profiles, interfaces of the same type are indistinguishable: only the multiset of types matters, not their ordering. The total contribution of all interfaces of type σtherefore lies in the symmetric tensor power Symh(σ)(Wσ), whose dimension is given by dim Symh(σ)(Wσ) = d0+h(σ)−1 h(σ)≤(d0+h(σ))d0−1. Since Pσh(σ)≤kR =O((log n)1+c), each individual h(σ)is at most O((log n)1+c), and thus dim Symh(σ)(Wσ)≤d0+O((log n)1+c)d0−1= (log n)O(1). The full contribution of the profile his contained in the tensor product Vh⊆O σ∈Σ≤q Symh(σ)(Wσ). The alphabet Σ≤qhas constant size M=O(1), so the dimension of this tensor product is bounded by dim Vh≤Y σ∈Σ≤q dim Symh(σ)(Wσ)≤(log n)O(1)M= (log n)O(1). This proves (2). Property (1) holds by construction: for any SPDP row whose local type evolution matches the profile h, each interface contribution lies in the corresponding Wσ, and the aggregate over all interfaces lies in the indicated tensor product. Finally, combining Lemma 12 (which gives |H| ≤ nO(1)) with the bound on dim Vhyields Γk,ℓ(p)≤X h∈H dim Vh≤(log n)O(1) ·|H| =nO(1), as claimed. Remark 3.We do not actually need the precise polylog bound dim Vh≤(log n)O(1); it suffices that dim Vh≤nO(1). Lemma 14 (Monomial/coordinate budget).Under (A1) and with degree guard ℓ=O(log n), the number of admissible monomial/coordinate choices per fixed profile is nO(1). 22 Proof. Each SPDP row corresponds to selecting at most ℓglobal variables among nand applying at most ℓlocal derivative coordinates, each supported on a radius-1neighborhood (A1). For each j∈ {0, . . . , ℓ}the number of ways to pick jglobal variables is n j≤nj. For each chosen variable, the number of admissible local derivative coordinates is bounded by a compiler-dependent constant B=O(1) (finite local alphabet and radius-1support in the diagonal basis). Hence ℓ X j=0 n jBj≤ ℓ X j=0 (Bn)j≤(ℓ+ 1) (Bn)ℓ=nO(ℓ)=nO(log n)=nO(1). The hidden constant depends only on Band the constant implicit in ℓ=O(log n). 2.3 Polynomial Width⇒Rank Theorem 15 (Polynomial Width⇒Rank).Let pbe any P-computable workload compiled by the deterministic radius-1compiler in the diagonal basis with Π+=A, under (A1)–(A4). Then for k, ℓ = Θ(log n)and R=C(log n)c, Γk,ℓ(p)≤RO(1) ·nO(1) =nO(1). Proof. Fix k, ℓ = Θ(log n)and let Wbe the set of canonical windows of length k, obtained via (C1) and (C2). By Lemma 11, the set Hof interface-anonymous profiles realizable by windows in Whas cardinality at most Rαfor an absolute constant α, independent of k. For a profile histogram h∈ H, consider the SPDP submatrix consisting of rows generated by windows with profile h. By Lemma 9, permutations of interface identities within blocks act by block-diagonal invertible left/right multiplications on this submatrix and therefore do not change its rank. It follows that the rank contribution of all windows with profile h is upper-bounded by the number of admissible monomial/coordinate choices consistent with h. By Lemma 14, this quantity is nO(1). Summing over profiles yields the bound. By the constant–type profile bound (Lemma 11), the number of interface–anonymous profiles is RO(1). For each fixed profile, the monomial/- coordinate budget is nO(1) (Lemma 14). Hence Γk,ℓ(p)≤RO(1) ·nO(1). Since R=C(log n)c, we obtain Γk,ℓ(p)≤nO(1), establishing the claim. Remarks. (1) The key change relative to earlier drafts is the interface-anonymous profile (Definition 12) plus Lemma 9, which removes an exponential dependence on Rthat would arise from tracking interface identities. (2) The rigorized (C2) guarantees a constant normalform length qper interface via a finite-monoid/rewriting argument, making the stars-andbars count in Lemma 11 valid and independent of the window length k. Consistency with the holographic principle. In the diagonal basis with Π+=A, (A1)–(A3) are compiler properties; (C2) is a local algebraic property (finite monoid / terminating rewrite system) induced by the same diagonalization. Thus the profile bound RO(1) is a structural consequence of the compiler and not of input size nor choices of k, ℓ = Θ(log n). 23 Lemma 16 (Restriction monotonicity).Let ρbe a (block–local) restriction/identification of variables and p′:= p↾ρ. Then for all k, ℓ,Γk,ℓ(p′)≤Γk,ℓ(p). Proof. Let Rρ:F[x1, . . . , xN]→F[x′ 1, . . . , x′ N′]be the linear substitution map induced by ρ. Differentiation on free variables commutes with substitution, hence for each generator u∂τpof the SPDP row–space we have Rρ(u∂τp) = u′∂τ′(p′)for suitable u′, τ′(variables eliminated by ρvanish; constants multiply coefficients). Therefore Rρspan{u∂τp}contains span{u′∂τ′p′}. Since Rρis linear, dim span{u′∂τ′p′} ≤ dim span{u∂τp}, i.e. Γk,ℓ(p′)≤ Γk,ℓ(p). Lemma 17 (Submatrix monotonicity).If M′is any submatrix of Mk,ℓ(p)obtained by selecting a subset of rows and/or columns, then rank(M′)≤Γk,ℓ(p). Proof. Selecting rows/columns corresponds to restricting the domain/codomain of the underlying linear map, which cannot increase rank. Lemma 18 (Affine/basis invariance).Let Φ : x7→ Ax +bwith A∈GLN(F). Then Γk,ℓ(p◦Φ) = Γk,ℓ(p)for all k, ℓ. Moreover, changing the monomial basis within blocks multiplies Mk,ℓ(p)on the left/right by block-diagonal invertible matrices, hence preserves rank. Proof. By the multivariate chain rule, ∂τ(p◦Φ) = P|σ|=|τ|ατ,σ (∂σp)◦Φ, where (ατ,σ)is the invertible minor map induced by Aon ∧|τ|FN. Multiplying by all monomials uof degree ≤ℓand expanding in the monomial basis shows that the SPDP row–space for p◦Φis the image of the SPDP row–space for punder an invertible linear operator (composition with Φon coefficients plus the minor map on partials). Dimensions are equal. The Π+map acts block-locally by an invertible linear operator on the column space; a change of monomial basis multiplies Mk,ℓ(p)on the left/right by block-diagonal invertible matrices. In either case, matrix rank is invariant. In particular, Π+acts block-locally by an invertible linear map on the column space (and dually on rows), so left/right multiplication by the corresponding block-diagonal change-ofbasis matrices preserves matrix rank; hence Γk,ℓ is invariant under Π+. Lemma 19 (Basis invariance).Changing the monomial order or coordinate basis multiplies Mk,ℓ(p)on the left/right by invertible matrices; hence Γk,ℓ(p)is basis–invariant. Proof. Immediate from rank(UPS) = rank(P)for any invertible U, S. Lemma 20 (Monotonicity Suite).The SPDP rank Γk,ℓ(p)satisfies the following properties: (a) Restriction monotonicity (Lemma 16): For any restriction ρ,Γk,ℓ(p↾ρ)≤Γk,ℓ(p). (b) Projection monotonicity (Lemma 17): Selecting a subset of rows or columns cannot increase rank. (c) Affine invariance (Lemma 18): For any invertible affine map Φ,Γk,ℓ(p◦Φ) = Γk,ℓ(p). (d) Basis invariance (Lemma 19): Changing monomial order or coordinate basis preserves Γk,ℓ(p). Proof. Follows immediately from Lemmas 16, 17, 18, and 19. 24 Conventions. Unless stated otherwise, pis the multilinear extension of a Boolean function; all ranks are over the base field F. When we say “SPDP rank” without parameters, the relevant (k, ℓ)are fixed in the surrounding statement. Invariance under Π+and block-local basis. Each allowed Π+or block-local basis change acts invertibly on the column space by left/right multiplication of Mk,ℓ(p)by blockdiagonal invertible matrices (over F), hence preserves rank exactly. Rank monotonicity under restriction and projection follows from functoriality of substitution and submatrix rank, respectively. Deterministic compiler model (canonical). The compilation from a uniform DTM to a local SoS polynomial is fixed and input-independent: radius-1templates, layered-wires and time×tape tiles, constant fan-in, diagonal local basis, and fixed Π+=A. Tag wires (phase_id,layer_id,clause_id,wire_role) are compiler-written constants. This yields per-access CEW =O(log log N)and global CEW ≤C(log n)cacross poly(n)accesses. Symbol Meaning ninput size Nnumber of compiled variables (after instrumentation), N= Θ(n) Bblock partition of variables; each block has radius r= 1 CEW(p)contextual entanglement width of compiled polynomial p MB k,ℓ(p)SPDP matrix, rows (τ, u), cols xβ, entries coeffxβ(u·∂τp) ΓB k,ℓ(p)rank over Fof MB k,ℓ(p) PM,n P-side compiled polynomial from DTM M QΦnNP-side clause-sheet SoS for instance Φn TΦblock-local extraction map (basis, affine, restriction, projection) Table 2: Notation used in the SPDP/CEW framework. 2.4 Classical Bridge: Equivalence to Standard Complexity Theory A crucial aspect of our approach is establishing formal equivalence between the observertheoretic definitions introduced above and standard complexity theory. Theorem 21 (Classical–Observer Equivalence).The following equivalences hold: 1. Pclassical =Pobserver where Pobserver ={L:∃Owith CEW(O)≤ncdeciding L} 2. NPclassical =NPobserver where NPobserver ={L:∃Vwith CEW(V)≤ncverifying L} 3. The epistemic complexity class EpistemicP ={L:∃Oobserver with bounded resolution deciding L} equals P 25 P Polynomial Γk,ℓ ≤nO(1) Theorem 64 NP Exponential Γk,ℓ ≥2Ω(n) Theorem 66 Exponential Gap No poly-time algorithm can bridge this gap SPDP Rank Gap: Pvs. NP The “God Move” (Section 20) extracts this separation deterministically: rank-monotone reduction + identity-minor lower bound ⇒P=NP (Theorem 143) Figure 5: Rank gap at matching parameters (NP lower bound). QΦnexhibits an identity-minor of size nΘ(log n)at (k, ℓ) = Θ(log n); this contradicts the P-side upper bound under the rank-monotone extraction TΦ. Deterministic layered branching programs A deterministic layered branching program (BP) over variables x1, . . . , xnis a directed acyclic graph with layers 0,1, . . . , L, a single source in layer 0, sinks in layer L, and width W= maxτ|Vτ|where Vτis the node set of layer τ. Each edge from layer τto τ+ 1 is labeled by a literal λe(x)∈ {1, xi,1−xi}. Semantics. Edges out of a node within a layer have disjoint literal labels whose evaluations partition {0,1}; thus for any input x∈ {0,1}nexactly one outgoing edge is taken at each visited node, yielding a unique layer-by-layer path. The length is L. Lemma 23 (Compilation Lemma (BP simulation of polytime)).If L∈Pis decidable in time nk, then for each nthere exists a deterministic layered BP Bnof length L′=nO(k)and width W=nO(1) computing χL↾{0,1}n. Justification. Unfold the configuration graph of the time-nkTM for nksteps; each 32 layer has at most poly(n)configurations and the transition is deterministic given the scanned symbol. Hence L′= Θ(nk),W= poly(n). (Any standard TM→BP simulation suffices.) We embed χLas a multilinear polynomial fL:{0,1}n→ {0,1}(and identify it with its unique multilinear extension over F). SPDP rank bound for bounded-width/length BPs For multilinear f, let Mℓ(f)be the ℓ-shifted partial-derivative matrix: its rows are indexed by pairs (S, α)with |S|=ℓand deg(α)≤ℓ; the (S, α)-row is the coefficient vector of α·∂ℓf/∂xSin the monomial basis. Write rkSPDP,ℓ(f) = rk Mℓ(f). We now prove the key lemma completely. Lemma 24 (BP→SPDP, fixed order — full proof).Statement. Let Bbe a deterministic layered BP of length L′and width Wover {0,1}n, and let fbe the multilinear polynomial it computes. For any fixed ℓ∈ {2,3}, rkSPDP,ℓ(f)≤(CℓW L′)dℓ, for absolute constants Cℓ, dℓdepending only on ℓ. (For concreteness one may take dℓ= 2ℓ+ 2.) Proof. We use a matrix product representation and a cylinder decomposition. (1) Matrix product form. Index each layer τ= 0, . . . , L′by a state set Vτwith |Vτ| ≤ W. Let s∈V0be the unique source and let A⊆VL′be the accepting sinks. For τ= 0, . . . , L′−1define the W×Wmatrix Mτ(x)whose (u, v)entry is the literal labeling the edge u→v(if present) and 0otherwise. Determinism per layer ensures: for fixed u∈Vτ, the nonzero entries in row uof Mτare disjoint literals in {1, xi,1−xi}(so their sum evaluates to 1 on any input). Let eube the standard basis vector for state u, and a=Pv∈Aev. Then f(x) = e⊤ sL′−1 Y τ=0 Mτ(x)a. All Mτare affine-linear in a single variable (or constant): each layer “queries” at most one input variable due to the partition property. (2) Differentiation localizes to layers. Fix an ℓ-set S={i1, . . . , iℓ}and a shift monomial αwith deg α≤ℓ. By Leibniz, α·∂ℓ xSf=X T⊆{0,...,L′−1},|T|=r≤ℓX ϕ:T→Sbij. e⊤ sL′−1 Y τ=0 B(T,ϕ) τ(x)a, where for τ /∈T,B(T,ϕ) τ=Mτ; and for τ∈Twe replace Mτby its (nonzero) partial derivative w.r.t. the unique variable xϕ(τ)used in that layer, multiplied by the appropriate factor coming from αif αuses xϕ(τ)at layer τ. Because Mτis affine-linear in its (single) layer variable, ∂Mτ/∂xiis a constant matrix with entries in {0,±1}. The multiplicative shift α can be distributed so that all its factors that live in layers of Tare folded into a constant-size linear combination of the same two literals {1, xi}(or {1,1−xi}) in those layers; factors from 33 other layers are absorbed into neighboring constant matrices (still constant rank-1 updates). Thus, for fixed (S, α), each summand is of the form e⊤ sL′−1 Y τ=0 f Mτa, where f Mτ∈Uτand each layer-local space Uτis a fixed-dimension linear space generated by {Mτ, I, ∂Mτ,and at most two literal-multiples of Mτ}. Hence dim Uτ≤Cfor an absolute constant Cindependent of n, W, L′(it depends only on the fixed set {1, xi,1−xi, ∂xi, ∂(1 −xi)}). (3) Cylinder decomposition by at most ℓtouched layers. Each summand touches exactly the layers in T(with |T|=r≤ℓ) where a derivative was taken; all other layers contribute Mτ∈Uτ(no derivative). For a fixed ordered r-tuple 0≤t1<··· < tr≤L′−1 (the layers in T), and for any choice of “cut” states u0∈V0, u1∈Vt1+1, . . . , ur∈Vtr+1, ur+1 ∈VL′, insert resolutions of identity Pv∈Vtj+1 eve⊤ v=Ibetween blocks to factor the product as e⊤ st1 Y τ=0 c Mτeu1 | {z } prefix P0(u1) ·t2 Y τ=t1+1 c Mτ | {z } middle block ···L′−1 Y τ=tr+1 c Mτa | {z } suffix Sr(ur) where each c Mτ∈Uτand in the rtouched layers we choose c Mtj∈ {∂Mtj,literal-modifications of Mtj}. After this bookkeeping, every summand is a scalar obtained by chaining r+ 1 block maps between cuts: X u1,...,ur P0(u1) |{z} ∈F ·L1(u1, u2) | {z } ∈F ···Lr(ur, ur+1) | {z } ∈F ·Sr(ur) |{z} ∈F . Crucially, for fixed choices of the touched layers and the local pattern (which derivative/literal option was used in each touched layer), each block Lj(·,·)is a bilinear form whose coefficient matrix has size ≤W×Wand belongs to a linear space of constant dimension (because Utj has constant dimension and we multiply a constant number of such matrices). Thus the whole family of such scalars lies in the linear span of the cylinder basis B:= {P0(·)·L1(·,·)···Lr(·,·)·Sr(·) : 0 ≤r≤ℓ, 0≤t1<··· < tr< L′,local patterns }, indexed by: •the choice of r≤ℓtouched layers (≤Pr≤ℓL′ r≤(eL′/ℓ)ℓ), •the cut state tuple (u0=s, u1, . . . , ur, ur+1 ∈A)(≤Wr+1 ≤Wℓ+1), •and a local derivative pattern per touched layer; because each layer contributes from the constant set {1, xi,1−xi, ∂xi, ∂(1 −xi)}, the number of distinct patterns is a constant cℓdepending only on ℓ. 34 Therefore, for fixed (S, α), every row polynomial α·∂ℓ xSflies in span(B). Moreover, the same cylinder basis Bworks uniformly for all (S, α)with |S|=ℓ,deg α≤ℓ, because (S, α) only determines which c Mtjwe pick inside the constant-size local menu. (4) Row-space bound. Let c(g)denote the coefficient vector of a polynomial gw.r.t. the monomial basis. The map g7→ c(g)is linear, hence {c(α·∂ℓ xSf) : |S|=ℓ, deg α≤ℓ} ⊆ span {c(b) : b∈B}. It follows that dim(rowspace of Mℓ(f)) ≤#B≤cℓ ℓ·Wℓ+1 ·X r≤ℓL′ r≤(CℓW L′)ℓ+1 for a constant Cℓdepending only on ℓ. (Here we use Pr≤ℓL′ r≤(eL′/ℓ)ℓ.) (5) Rank bound. Since the rank of Mℓ(f)is at most its row-space dimension, we obtain rkSPDP,ℓ(f)≤(CℓW L′)dℓ with dℓ:= ℓ+ 1. To absorb constant-factor overheads from prefix/suffix linearizations one may inflate to dℓ= 2ℓ+ 2 without changing polynomial dependence. This completes the proof. Theorem 25 (P-languages admit polynomial SPDP rank).Statement. Let L∈Pbe decidable in time t(n) = nk. For each fixed ℓ∈ {2,3}, there exists c=c(k, ℓ)such that rkSPDP,ℓ(χL)≤nc. Equivalently, rkSPDP(χL) = nO(k)for fixed ℓ. Proof. By the Compilation Lemma, χLat length nis computed by a layered BP with L′=nO(k)and W=nO(1). Apply Lemma 24: rkSPDP,ℓ(χL)≤(CℓWL′)dℓ=nO(k). Corollary 26 (P⊆Low SPDP Rank).For every L∈Pthere exists csuch that, for all n, rkSPDP(Ln)≤nc, where Lnis Lrestricted to inputs of length n. Proof. Apply Theorem 25 for a fixed ℓ∈ {2,3}and take the maximum over ℓ. Remark 5 (Multilinearization and Boolean agreement).If the compiled polynomial uses nonmultilinear terms, replace xr iby xifor r≥1to obtain the multilinearization fml. Then fml = χLon {0,1}n. The SPDP construction reads coefficients of shifted derivatives; restricting to {0,1}nand to the path-polynomial span can only reduce the matrix, so rkSPDP,ℓ(fml)≤ rkSPDP,ℓ(f). 35 3.2 Low-rank ⇒P (Deterministic Interpolation Algorithm) [Optional] This section is not used in the separation proof. It shows that low SPDP rank yields a deterministic sparse-basis representation and hence a polynomial-time decision procedure. Throughout, fix a constant derivative order c∈ {2,3}. Theorem 27 (Sparse-basis recovery in polytime — Optional).Let f(x1, . . . , xn)be a degreedpolynomial over a field Fwith rkSPDP,c(f)≤n6. There is a deterministic algorithm running in nO(c)time that outputs 1. a monomial basis Bof size |B| ≤ n6, and 2. the coefficient vector of fin that basis. Consequently, the decision problem computed by fcan be solved in time O(n6)by evaluating the recovered sparse form. Setup and primitives Field/degree. Work over characteristic 0(or any prime p > poly(n)) so all linear algebra and finite-difference identities are valid. Use the standard Kronecker substitution with base B= poly(n)when needed so all induced univariate degrees are poly(n). Rows via finite differences (order c). For any point x∈ {0,1}nand any |S| ≤ c, the mixed partial ∂|S|f/∂xSat xcan be computed by a linear combination of at most 2|S|≤2c evaluations of fat Hamming neighbors of x. Thus each value of α·∂≤cf(for deg α≤c) costs O(2c)black-box evaluations of f. TM simulation oracle. Each evaluation f(y)can be computed by simulating the deciding TM in time nk. Hence each row evaluation above costs O(2cnk). Columns as monomial functionals. For a monomial m(x), the value α·∂≤cmat any xis explicit: it is either 0or a {±1}-multiple of a (lower-degree) monomial evaluated at x. Therefore we can compute column entries for monomials without querying f. Hitting set for determinism. Use your explicit hitting set H(seed length O(log n); see §17.7.4) to choose evaluation configurations that guarantee full-rank minors for any column subfamily of size ≤n6. Concretely, we select T= Θ(n6)row functionals Ej(·) = αj(x)·∂|Sj|(·)/∂xSjevaluated at x(j)∈H, with |Sj| ≤ cand deg αj≤c, so that the T×rmatrix [Ej(m)]j,m∈Bis nonsingular for every monomial set Bof size r≤n6. Algorithm 12′(Deterministic SPDP-Basis Recovery) Input: oracle for fvia TM simulation; parameters n, k, c; degree bound d. Output: a monomial basis Bwith |B| ≤ n6and coefficients {ˆ fm:m∈B}such that f=Pm∈Bˆ fmm. 36 1. Build the measurement vector (rows from f). Choose T= Θ(n6)configurations {(x(j), Sj, αj)}T j=1 as above from the hitting-set schedule. For each j, compute bj:= Ej(f) = αj(x)·∂|Sj|f/∂xSjx=x(j) using at most 2cevaluations of fat nearby points (finite differences). Cost: T· O(2cnk) = O(nk+6). 2. Deterministic rank-revealing column selection (no enumeration). We access columns implicitly: given a monomial m, we can compute the column vector v(m) := (E1(m), . . . , ET(m)) ∈FT in poly(n)time (each entry is a trivial symbolic derivative of mevaluated at x(j)). Run a deterministic rank-revealing procedure (e.g., greedy Gaussian elimination with exact arithmetic, or RRQR over the implicit column oracle) that iteratively adds m’s whose v(m)increases the span on FTuntil the span contains b= (b1, . . . , bT). By the low-rank premise, the column space of Mc(f)has dimension ≤n6. Our hittingset choice ensures that some set of ≤n6monomial columns is independent under {Ej}. The procedure returns such a set B={m1, . . . , mr},r≤n6, and coefficients γ∈Fr with b= r X i=1 γiv(mi). 3. Recover the actual coefficients of fon B. Pick any rfresh points y(1), . . . , y(r)∈H. Form the linear system f(y(ℓ)) = r X i=1 ˆ fmimi(y(ℓ)) (ℓ= 1, . . . , r), using TM simulation to obtain the left-hand side. The r×rmatrix [mi(y(ℓ))] is a Vandermonde-type/evaluation matrix that is nonsingular by the hitting-set guarantee. Solve for ˆ fmi. Complexity. •Evaluations: O(r) = O(n6)points, each in time nk⇒O(nk+6). •Linear algebra: solve an r×rsystem in O(rω) = O(n6ω)time (conservatively, O(n18)). •Column-oracle arithmetic is poly(n)per pivot and dominated by the terms above. Overall runtime: nO(c)(with cfixed and all exponents polynomial in k). 37 Correctness Low rank ⇒small column dimension. rkSPDP,c(f)≤n6means the column space of the ℓ-shifted partial-derivative matrix (for ℓ=c) has dimension ≤n6. Columns are indexed by monomials (up to the relevant degree). Hence there exists a monomial set B of size ≤n6whose columns form a basis of that space. Hitting-set soundness. The chosen measurement functionals {Ej}(shifted-derivative evaluations at Hpoints) induce a linear map that is injective on every ≤n6–dimensional column subspace; equivalently, for any such B, the matrix [Ej(m)]j,m∈Bis nonsingular. Rank-revealing selection finds B.Since b= (Ej(f))jis a linear combination of monomial columns within that space, the deterministic rank-revealing routine selects a spanning set Bof size ≤n6and expresses bin that basis. Coefficient recovery is unique. The evaluation matrix [mi(y(ℓ))] over His full rank for |B|points, so the coefficients {ˆ fmi}are uniquely determined. Decision procedure. The recovered representation f(x) = Pm∈Bˆ fmm(x)evaluates in O(|B|) = O(n6)time on any input x. Thus the underlying language is decidable in polynomial time. Remark 6 (What we did not assume).We did not assume Fourier sparsity or use the Mansour–Shi learner. We only used: (i) the low SPDP-rank hypothesis; (ii) explicit hitting sets (from §17.7.4); (iii) TM simulation for evaluations; and (iv) standard finite-difference identities and deterministic linear algebra. 3.3 Bridge Between Partial-Derivative and SPDP Rank 3.3.1 Complete Bridge Proof We compare the classical partial-derivative coefficient matrix against the global SPDP matrix (i.e., SPDP rows taken over all derivative orders ℓ≥0, with shift αranging over all monomials; this section does not restrict ℓto {2,3}). Definition (Partial-derivative coefficient matrix). Fix a partition [n] = S⊔T. For a multilinear polynomial p∈F[x1, . . . , xn], let MS={xU:U⊆S}, MT={xV:V⊆T} be the monomial families over Sand T. The matrix PDS,T (p)∈FMT×MS has rows indexed by xV∈MTand columns by xU∈MS, with entry PDS,T (p)V,U := [xVxU]p, the coefficient of the monomial xVxUin p. 38 Definition (Global SPDP matrix). Let MSPDP(p)be the (row-concatenated) matrix whose rows are the coefficient vectors of α·∂|R| xRpin the full monomial basis over [n], ranging over all pairs (R, α)with R⊆[n]and αany monomial (no degree cap needed for multilinear p). Its rank is the global SPDP rank, rkall SPDP(p). (Your main theorems only use fixed orders ℓ∈ {2,3}; here we allow all orders purely for this comparison lemma.) Lemma 28 (Partial derivatives form a submatrix).For multilinear pand any partition [n] = S⊔T, rank PDS,T (p)≤rank MSPDP(p)= rkall SPDP(p). Proof. Fix S, T as above. For each U⊆S, consider the SPDP row corresponding to (R= U, α = 1); this row is the coefficient vector of ∂|U| xUp. Because pis multilinear, ∂|U| xUp=X V⊆T[xVxU]pxV, i.e., its support lies entirely in monomials over T, and the coefficient of xVequals the coefficient of xVxUin p. Now restrict the columns of the global SPDP matrix to the monomials over T(i.e., keep only columns indexed by xVwith V⊆T), and restrict the rows to the subset {(R=U, α = 1) : U⊆S}. On this block, the entry at row U, column Vis precisely [xV]∂|U| xUp= [xVxU]p. Therefore this block is exactly PDS,T (p)⊤(the transpose of PDS,T (p)). Hence PDS,T (p)(up to transposition) is a literal submatrix of MSPDP(p). Submatrix rank never exceeds the ambient rank, so rank PDS,T (p)≤rank MSPDP(p). Remark 7 (Why we didn’t use evaluations).An “evaluation matrix” E[a, b] = p(a)would be rank-1 and unrelated to SPDP. The bridge is purely coefficient-level: SPDP rows are coefficient vectors of shifted partials; choosing α= 1 and varying R⊆S, then projecting to columns over T, recovers the classical ∂-matrix. 3.4 Barrier Transcendence Arguments This section shows that our method does not relativize (§2.4.1) and is not a natural proof in the algebraic sense (§2.4.2). These results are used later in §9 (Barrier Immunity Summary). 3.4.1 Relativization Barrier — Complete Proof Theorem 29 (Non-relativizing method).There exists an oracle Asuch that PA=NPA[17], while our SPDP lower bounds remain valid relative to A. Consequently, the proof technique of §2 (which combines the upper bound P⊆LowSPDP with explicit SPDP lower bounds) does not relativize. 39 Proof. Take A= QBF (PSPACE-complete). It is standard that PA=NPA= PSPACE. Hence no relativizing proof can separate PAfrom NPA. Now observe two facts about our technique: Algebraic lower bounds persist. Any algebraic lower bound for the SPDP rank of a fixed polynomial (e.g., Permn) is a statement internal to coefficients/derivatives and is independent of an oracle on a Turing machine. Thus, for every oracle A, rkA SPDP,ℓ(Permn) = rkSPDP,ℓ(Permn)≥2Ω(n)(for fixed ℓ), by the same algebraic argument as in the unrelativized world. In particular, the exponential lower bound rkSPDP,ℓ(Permn)≥2Ω(n) arises from the Lagrangian analysis developed in §14.2, where the non-degeneracy of the Lagrangian potential L(Φ) ensures exponential independence among shifted partial derivatives. We reference this formal derivation later when completing the lower-bound half of the separation. The upper bound P⊆LowSPDP need not relativize. Our upper bound proceeds via branching programs without oracle gates (§2.1). A PA-machine can make oracle queries that cannot, in general, be simulated within the BP→SPDP pipeline under the same parameters. Therefore we cannot conclude PA⊆LowSPDP. Putting these together: for A= QBF we have PA=NPAwhile the SPDP lower bounds continue to hold. Hence our proof technique is non-relativizing. Remark 8.One may replace Permnwith any explicit polynomial for which the paper proves an ℓ-SPDP rank lower bound of 2Ω(n); the statement remains the same. 3.4.2 Natural Proofs Barrier — Algebraic Non-Naturality (Complete) The Razborov–Rudich “natural proofs” framework [21] demands (i) largeness (the property holds for a 2−O(n)fraction of Boolean functions) and (ii) constructivity (decidable in poly(n) given a truth table). We show that the low-SPDP-rank property used by our upper bounds fails both requirements in an algebraic sense. This suffices to explain why our method evades the Natural Proofs barrier. Fix a derivative order ℓ∈ {2,3}and a polynomial bound r(n) = nO(1). Define Plow(n) := {f: rkSPDP,ℓ(f)≤r(n)}. Theorem 30 (Algebraic non-naturality of low SPDP rank).For each n,Plow(n)is (i) not large in the algebraic sense (Zariski-meagre / measure-zero in coefficient space), and (ii) not constructive from truth tables in poly(n)time. Hence the SPDP-rank property used by our framework is not “natural”. 40 Proof. (i) Not large (algebraic). Fix a degree bound d(as in our Boolean→polynomial embedding). View fas a point in the coefficient space FN, where N= d X i=0 n i=n ≤d. For each f, the ℓ-SPDP matrix Mℓ(f)has entries that are polynomial functions of the coefficients of f. The condition rk Mℓ(f)≤rholds iff all (r+ 1) ×(r+ 1) minors of Mℓ(f) vanish—i.e., flies in the common zero set of a finite family of polynomials in FN. Therefore Vr,ℓ := {f: rkSPDP,ℓ(f)≤r} is a proper algebraic variety (strictly lower dimension than N) whenever the generic rank exceeds r(which holds for all polynomial r(n)in our degree regime). Hence Vr,ℓ has Lebesgue measure zero over R, and negligible measure over any sufficiently large finite field. In particular, the property is not large in the algebraic sense. (ii) Not constructive (truth-table input). Suppose we are given the full truth table of f:{0,1}n→ {0,1}(size 2n). To decide whether rkSPDP,ℓ(f)≤r, one must, in general, compute (or certify) the rank of Mℓ(f). Even forming the relevant portion of Mℓ(f)requires enumerating monomials up to degree d= Θ(n), whose count is N= d X i=0 n i= 2Θ(n). Any exact algorithm must perform at least Ω(N)arithmetic operations just to read the induced data, and rank computation takes Ω(N2)field operations in the worst case. Since N= 2Θ(n), this is superpolynomial in n. Therefore the property is not decidable in poly(n) time from the truth table (i.e., it is not constructive in the Razborov–Rudich sense). Remarks. •We intentionally avoid claiming #P-hardness; the unconditional size-of-matrix argument already suffices to violate constructivity. •If one restricts to random polynomials with full-dimensional coefficient distributions, part (i) strengthens to “probability 0” for low rank; we do not need a finer Boolean density bound here. Conclusion of §2.4.1–2.4.2. The algebraic lower bounds we use persist under oracles, while the upper bound P⊆LowSPDP does not relativize, so the technique is non-relativizing. Moreover, the low-rank property is algebraically meagre and not constructive from truth tables, so the method evades natural proofs in the relevant sense. 41 of rank t. Equivalently, the column space of Mis a t-dimensional subspace of FR q, and M maps the standard basis of FC qinto this subspace via a surjective linear map. To count, we: (i) Choose a t-dimensional column space V⊆FR q: there are at most qRt choices (each subspace is determined by a full-rank R×tmatrix). (ii) Choose a surjective linear map FC q→V: any such map is determined by the images of the Cstandard basis vectors, each lying in the t-dimensional space V, giving at most qCt choices. Multiplying yields qRt ·qCt =qt(R+C). However, this overcounts by the automorphism group of the pair (V, basis of V), which is GLt(Fq)of size roughly qt2. Hence the number of rank-t matrices is at most qt(R+C)/qt2=qt(R+C−t). Summing over t= 0, . . . , r gives the stated bound #{R×Cmatrices of rank ≤r} ≤ r X t=0 qt(R+C−t). This completes the justification. Set r=nc. Since R= Θ(nO(ℓ))and C= 2n, we have Pr rk(Mℓ(f)) ≤nc≤q−Ω(R C)=q−Ω(nO(ℓ)·2n)≤2−Ω(2n). Therefore |Fn,c|/22n≤2−Ω(2n), as claimed. Consequences for Natural Proofs. 1. Largeness fails. The density 2−Ω(2n)is far below the Razborov–Rudich threshold 1/poly(2n). 2. Constructivity is moot. Since the property is vanishingly small, the natural-proofs barrier does not apply even if membership were decidable in 2O(n)time. Hence, the property “rkSPDP,ℓ(f)≤nc” is non-natural unconditionally. Theorem 35 (Evaluation from a low-rank certificate).Let f:{0,1}n→ {0,1}be a Boolean function and fix an order ℓ≥0. Suppose we are given a low-rank certificate for fconsisting of: 1. a rank factorization of the order-ℓSPDP matrix, Mℓ(f) = U V, U ∈FR×r, V ∈Fr×C, r = rkSPDP,ℓ(f), where R= Θ(nO(ℓ))and C= 2n; 2. and an implicit column application routine that, on input x∈ {0,1}n, computes V χ(x) in poly(n, r)time, where χ(x)∈FCis the monomial-evaluation vector χ(x)m=m(x). 48 Then f(x)can be evaluated in time poly(n, r). Remarks on the assumption. (i) For the global SPDP matrix (concatenating all derivative orders, including ℓ= 0), the ℓ= 0 block is the coefficient vector of f; in that case the extractor below is trivial. (ii) For the compiled classes we work with (§2.1, PAC/ABP routes), the matrix factorizations U, V inherit structure that supports fast column application x7→ V χ(x)(e.g., via product-of-small factors), so the assumption holds in our use-cases. Proof. Write c∈FCfor the coefficient vector of fin the multilinear monomial basis. Then for any input x, f(x) = ⟨χ(x), c⟩=χ(x)⊤c. Because Mℓ(f) = UV has rank r, the row-space and column-space coincide with the images of Uand V⊤, respectively. There exists a (precomputable) linear extractor E∈FC×R of size poly(n)such that c=E Mℓ(f)⊤y=E V ⊤U⊤y for some y∈FR(intuitively: Epicks a fixed linear combination of order-ℓshifted-derivative rows that inverts the differential operator back to coefficients; when the global SPDP is used, one can take Eto be the trivial selector of the ℓ= 0 block). Precompute a left-inverse L∈Fr×Rfor Uon the image of U(e.g., via rank-revealing QR/Bareiss on U), so LU acts as the identity on im(U). Then f(x) = χ(x)⊤c=χ(x)⊤E V ⊤U⊤y= (V χ(x))⊤(E⊤y′),where y′:= U⊤y∈im(U⊤). The vector z(x) := V χ(x)∈Frcan be computed in poly(n, r)time by hypothesis (implicit column application). The multiplier w:= E⊤y′∈Fris independent of xand is precomputable in poly(n, r)time from the certificate by solving a small linear system that pins c(or, in the global SPDP case, by directly selecting the ℓ= 0 block). Therefore, f(x) = ⟨z(x), w⟩, and evaluating f(x)takes O(r)field operations once z(x)is available. Overall cost is poly(n, r). No circularity arises: we never query fas an oracle; we only use the low-rank factorization and the fixed extractor Eprovided by (or precomputable from) the certificate structure of the compiled class. Summary. Lemma 34 shows that low SPDP rank is an exponentially rare property among Boolean functions, unconditionally ruling out “largeness” in the sense of Natural Proofs. Theorem 35 explains that, for the compiled classes we manipulate, a low-rank certificate gives polynomial-time evaluation, aligning with our P-side uniform collapse and keeping the framework non-circular. 49 3.9 Putting It All Together With Theorem 35, the deterministic kernel-vector construction, and the unconditional nonnaturality result, all logical dependencies in the proof of P=NP are now closed. The framework integrates the upper and lower bounds, the witness construction, and the barrier immunity arguments into a coherent, non-circular whole. Checklist. ✓Exponential SPDP-rank lower bound for #3SAT →diagonalizable separation. ✓Polynomial-time evaluation from low rank (no circularity). ✓Deterministic kernel vector w∈V⊥ nserving as a polynomial-time witness. ✓Barrier arguments bypass both natural-proofs and relativization. ✓Entire logical chain closed within the algebraic-analytic framework. 4 Note on Lean Formalization and Completion The argument developed so far is entirely formalizable in Lean 4, requiring only the standard definitions of P,NP, and polynomial-time verifiers. Completing the Lean proof involves three modules corresponding to the core results of Section 2: Polynomial upper bound (P⊆Low SPDP). The formal structure comprises: polynomial upper bound (P-side collapse), exponential lower bound (NP-side hardness), orthogonal witness construction (God Move), and the main separation theorem. 5 Observer Model: CEW-Bounded Computation 5.1 Observer frame and CEW We quantify an observer’s representational capacity by the Contextual Entanglement Width (CEW)—the largest number of inputs that can “jointly interact” in its multilinear representation. Definition 14 (Multilinear representation and CEW).Fix a field Fof characteristic 0or a sufficiently large prime. For a Boolean function f:{0,1}n→ {0,1}, let ˜ f∈F[x1, . . . , xn]be its unique multilinear polynomial that agrees with fon {0,1}n: ˜ f(x) = X S⊆[n] ˆ f(S)xS, xS:= Y i∈S xi. Define CEW(f) := max{|S|:ˆ f(S)= 0 } (i.e., CEW(f) = deg( ˜ f)). 50 Definition 15 (Observer classes).For each n, let PolyObsn:= {f:{0,1}n→ {0,1} | CEW(f)≤nO(1) }, ExpObsn:= {f:{0,1}n→ {0,1} | CEW(f)≤2Θ(n)}. Proposition 36 (BP degree ⇒polynomial CEW).Let Bbe a deterministic layered branching program (BP) of length Lover variables x1, . . . , xnwith edge labels in {1, xi,1−xi}, and let fbe its computed function. Then CEW(f)≤L. Proof. Each accepting path contributes a path polynomial given by the product of its Ledge labels; hence degree ≤L. Multilinearization does not increase degree, and summing paths preserves the maximal degree bound. Thus deg ˜ f≤L. Corollary 37 (P⊆PolyObs via BP compilation).If a language L∈Pis decidable in time nk, then for each nthe characteristic function χLadmits a representation with CEW(χL)≤ nO(k). Hence χL∈PolyObsn. Proof. By the polytime→BP compilation (Section 2.1), χLis computed by a layered BP of length L′=nO(k). Apply Proposition 36. 5.2 From SPDP rank to CEW We relate SPDP rank to CEW: bounded CEW limits the column space of the SPDP matrix for any fixed derivative order. Lemma 38 (Degree bounds columns ⇒rank bound).Let f:{0,1}n→ {0,1}have multilinear degree d= CEW(f). Fix any constant order ℓ≥0. Then rkSPDP,ℓ(f)≤ d X j=0 n j. Proof. An order-ℓrow of the SPDP matrix Mℓ(f)is the coefficient vector of α·∂|R|fwith |R|=ℓand deg α≤ℓ. Differentiation lowers degree by ℓ, the shift by αadds ≤ℓ, so the resulting degree ≤d. Thus no column indexed by a monomial of degree > d can appear with a nonzero coefficient in any row. The column space lies in the span of monomials of degree ≤d, whose number is Pd j=0 n j. Rank is at most the column-space dimension. Lemma 39 (Exponential SPDP rank ⇒linear CEW).Fix ℓ≥0. Suppose a family {fn} satisfies rkSPDP,ℓ(fn)≥2γn for some constant γ > 0. Then CEW(fn)≥c n for some constant c=c(γ)>0and all sufficiently large n. 51 Proof. Let dn= CEW(fn). If dn≤δn for δ∈(0,1), then by Lemma 38 rkSPDP,ℓ(fn)≤ ⌊δn⌋ X j=0 n j≤2H(δ)n, where His the binary entropy. Choosing δ < H−1(γ)yields 2H(δ)n<2γn for large n, a contradiction. Hence dn≥cn with c:= H−1(γ)>0. Corollary 40 (Classical ∂-LB ⇒large CEW).If {pn}has rank(PDSn,Tn(pn)) = 2Ω(n)for some |Sn| ≤ ℓ, then CEW(pn)≥Ω(n). Proof. By the uniform-monotonicity bridge (Sections 2.6–2.7), rkSPDP,ℓ(pn)≥2Ω(n). Apply Lemma 39. Corollary 41 (Entropy-tight CEW vs. SPDP rank).For any ℓ≥0and any f:{0,1}n→ {0,1}, minnd: d X j=0 n j≥rkSPDP,ℓ(f)o≤CEW(f)≤n. In particular, if rkSPDP,ℓ(f)≥2γn then CEW(f)≥(H−1(γ)−o(1)) n; conversely, if CEW(f)≤δn then rkSPDP,ℓ(f)≤2H(δ)n. Proof. The left inequality is Lemma 38 inverted (monotonicity of the cumulative binomial sum); upper bound CEW(f)≤nis trivial. The entropy-form bounds are the standard estimates for Pj≤δn n j. 5.3 Epistemic complexity classes We mirror classical P/NP inside the observer/CEW model. Definition 16 (Epistemic P).EpistemicP(n)is the set of f:{0,1}n→ {0,1}with CEW(f)≤nO(1). Definition 17 (Epistemic NP).EpistemicNP(n)is the set of f:{0,1}n→ {0,1}for which there exists a polynomial pand a polynomial-time verifier Vsuch that f(x) = 1 ⇐⇒ ∃w∈ {0,1}≤p(n)V(x, w) = 1, and, for each fixed w, the acceptance predicate x7→ V(x, w)has CEW ≤nO(1). Remark 12.For standard NP predicates (e.g., CNF-SAT), acceptance is local/low-degree, hence the CEW bound holds automatically. 52 5.4 Observer resource separation and EpistemicP ⊊EpistemicNP Theorem 42 (Observer hierarchy).For every n,PolyObsn⊊ExpObsn. Proof. Inclusion is immediate. For strictness, take a hard family {fn}(Lagrangian/Tseitin; cf. §6/§14) with exponential classical ∂-matrix rank; by Corollary 40, CEW(fn)≥Ω(n), so fn∈ExpObsn\PolyObsn. Theorem 43 (Epistemic P⊊NP).For all sufficiently large n, EpistemicP(n)⊊EpistemicNP(n). Proof. (Inclusion) If f∈P, Corollary 37 gives CEW(f)≤nO(1), hence f∈EpistemicP(n)⊆ EpistemicNP(n)(take empty witness). (Strictness) Let {fn}be the explicit NP family from the Lagrangian/Tseitin construction (e.g., 3-SAT on expander templates). These have polynomial-time verifiers, so fn∈EpistemicNP(n). By Corollary 40, CEW(fn)≥Ω(n), thus fn/∈EpistemicP(n). Remark 13 (Observer dualization).Within the N-Frame observer-centric reading, constructing a global dual w∈V⊥ n(Section 2.7) is the “God-move”: it algebraically collapses the polynomial-time subspace to its orthogonal complement, exposing (via CEW and SPDP) the resource boundary between what polynomial observers can compute and what they can only verify. 6 The Observer–Classical Bridge: Formal Equivalence of Computational Frameworks 6.1 Resource-Bounded Separation (Formal Statement) We summarize the separation in purely algebraic/observer terms, using results established in §2 (BP→SPDP upper bounds; uniform-monotonicity bridge; witness construction) and §4 (CEW vs. SPDP). Theorem 44 (Resource-bounded separation).Fix any constant derivative order ℓ∈ {2,3}. There exists an explicit family {fn}such that 1. (Upper for P)For every g∈P,rkSPDP,ℓ(gn)≤nO(1) and CEW(gn)≤nO(1). 2. (Lower for the hard family) rkSPDP,ℓ(fn)≥2Ω(n)and therefore CEW(fn)≥Ω(n). 3. (Observer separation) EpistemicP(n)⊊EpistemicNP(n)(Theorem 43), witnessed by {fn}. Proof (summary). (1) follows from §2.1 (polytime→BP→SPDP) and Proposition 36. (2) follows from the Lagrangian/Tseitin lower bound (see §6/§14) plus the ∂-to-SPDP bridge (§2.6–§2.7). (3) is Theorem 43. 53 6.2 SPDP Theory: Multilinear Foundations (What We Actually Use) We collect only the identities needed for §2–§4 (and used implicitly in §6). Lemma 45 (Unique multilinearization).Every f:{0,1}n→ {0,1}has a unique ˜ f∈ F[x1, . . . , xn]multilinear with ˜ f|{0,1}n=f. Lemma 46 (Degree = CEW). deg( ˜ f) = CEW(f) = max{|S|:ˆ f(S)= 0 }. Lemma 47 (Column bound for order-ℓSPDP; cf. §4.2).If CEW(f) = d, then rkSPDP,ℓ(f)≤ d X j=0 n j. Lemma 48 (Uniform monotonicity; cf. §2.6–§2.7).For any partition [n] = S⊔Twith |S| ≤ ℓ, the partial-derivative matrix PDS,T (f)appears (up to transpose) as a submatrix of the order-ℓSPDP matrix. Hence rank(PDS,T (f)) ≤rkSPDP,ℓ(f). Corollary 49 (Entropy-tight CEW↔SPDP; cf. §4.2).If rkSPDP,ℓ(f)≥2γn then CEW(f)≥ (H−1(γ)−o(1)) n; if CEW(f)≤δn then rkSPDP,ℓ(f)≤2H(δ)n. Remark 14.These are the precise tools you actually use later; the previous “eval monomial” items can be dropped. 6.3 Observer–Classical Bridge (Exact Compilation) We formalize the exact match between classical computation and the observer/CEW picture. Theorem 50 (Exact polytime→observer compilation).Let Mbe a polynomial-time decider for L. There exists a layered BP Bnof length nO(1) and polynomial width such that the Boolean function fn=χLcomputed by Mat length nequals the function computed by Bn. Consequently, CEW(fn)≤nO(1),rkSPDP,ℓ(fn)≤nO(1) (ℓ∈ {2,3}). Proof. Standard TM→BP simulation yields Bnwith length nO(1) and width nO(1) (cf. §2.1). Proposition 36 gives the CEW bound; §2.1 gives the SPDP bound. Theorem 51 (Explicit hard family ⇒observer separation).Let {fn}be the Lagrangian/Tseitin family (see §6/§14) with rank(PDSn,Tn(fn)) = 2Ω(n)for some |Sn| ≤ ℓ. Then CEW(fn)≥Ω(n)and rkSPDP,ℓ(fn)≥2Ω(n). Hence fn/∈PolyObsnbut fn∈EpistemicNP(n). Proof. Uniform-monotonicity (Lemma 48) transfers the ∂-LB to SPDP; Lemma 47/Cor. 49 lower-bound CEW. Verifiability is standard (NP witness), so fn∈EpistemicNP(n). 54 6.4 Mathematical Soundness: Global Dual and Non-Circularity We consolidate the witness construction and correctness guarantees. Theorem 52 (Deterministic dual w∈V⊥ n; cf. §2.7).Let Vnbe the span of the compiled “P-side” evaluations (rows chosen by the fixed triple-shift scheme). There is a deterministic algorithm running in ˜ O(n12)bit time that outputs a nonzero w∈V⊥ n. Proof. Assemble the triple-shift moment matrix Aof size r×rwith r≤n3; compute a nonzero left-kernel vector by Bareiss; verify orthogonality on a finite hitting set H= [n]3. See §2.7 for details and bit-size bounds. Theorem 53 (Completeness and Soundness of the certificate).Let wbe as above. Then: 1. (Completeness) For every g∈P(compiled by the fixed pipeline), ⟨w, g(·+h)⟩= 0 for all indexed shifts h∈[n]3. 2. (Soundness) For the hard family fn(Lagrangian/Tseitin), ⟨w, fn(·+h⋆)⟩ = 0 for some fixed h⋆∈[n]3. Proof. Completeness: w∈V⊥ nby construction, and Vncontains all compiled P-side rows indexed by [n]3. Soundness: the exponential SPDP/CEW lower bounds guarantee that the hard family escapes the compiled low-rank span; the fixed index set contains a witness shift with nonzero projection (as in §2.7). Corollary 54 (Non-circular evaluation).Given a low-rank certificate for g(rank factorization with efficient column application), g(x)can be computed in poly(n, rkSPDP,ℓ(g)) time (Theorem 35). Together with Theorem 53, the separation uses only algebraic certificates and fixed compilation—no oracle calls to the target function—so the argument is non-circular. 7 Epistemic Complexity Classes and the Observer Hierarchy Building on the observer–classical bridge (§5), we formalize epistemic complexity classes— computational classes defined by the inferential limits of bounded observers—so that they align cleanly with classical P/NP while preserving the CEW lens developed in §§2–4. Remark 15 (Purpose of this section).This section is included only to situate the algebraic and SPDP-rank arguments within the broader observer-theoretic framework developed elsewhere. It is not required for any formal theorem in this paper, but it helps clarify the conceptual origin of the CEW and “observer” terminology used throughout. Readers may view it as an interpretive bridge connecting the present proof architecture to a wider theory of bounded observers and epistemic computation. 55 7.1 Observers and CEW We retain CEW as in §4: for a Boolean f:{0,1}n→ {0,1},CEW(f) = deg( ˜ f)where ˜ fis the multilinear extension. An observer is simply an algorithm; we annotate it with two resources: •time bound T(n), •representation bound B(n)controlling the maximal CEW of any intermediate multilinear form it materializes (including ˜ fitself). We do not claim CEW alone bounds time; the time bound is part of the model. 7.2 Epistemic classes (definitions matched to classical ones) Definition 18 (EpistemicP).EpistemicP(n)is the set of f:{0,1}n→ {0,1}computable by an observer that runs in time nO(1) and whose intermediate CEW is bounded by nO(1). Let EpistemicP := SnEpistemicP(n). Definition 19 (EpistemicNP).EpistemicNP(n)is the set of f:{0,1}n→ {0,1}for which there exists a polynomial pand a verifier running in time nO(1) such that f(x)=1 ⇐⇒ ∃w∈ {0,1}≤p(n)V(x, w)=1, and for each fixed w, the acceptance predicate x7→ V(x, w)has CEW ≤nO(1). Let EpistemicNP := SnEpistemicNP(n). Remark 16.(i) The time bounds make the equalities with classical classes straightforward (see below). (ii) The CEW constraints record that the representations used by the observer are low-degree (consistent with §2’s BP→SPDP and §4’s CEW analysis). 7.3 Basic facts and equivalences Proposition 55 (BP length ⇒CEW/evaluation bounds).If a layered BP of length Land width Wcomputes f, then CEW(f)≤Land f(x)can be evaluated in poly(n, L, W)time. Proof. As in §4, Proposition 36; evaluation is a single path aggregation over Llayers. Theorem 56 (Epistemic–classical equivalence). EpistemicP = P, EpistemicNP = NP. Proof. P⊆EpistemicP: By §2.1, any P-time decider compiles to a BP with L=nO(1); by Proposition 55, CEW ≤nO(1) and time remains polynomial. EpistemicP ⊆P: By definition, observers in EpistemicP run in polynomial time; hence the computed functions lie in P. The NP case is identical: the verifier runs in polynomial time by definition, so EpistemicNP ⊆ NP; conversely any NP verifier has low-degree acceptance predicates (local checks), placing it in EpistemicNP. 56 7.4 Hierarchy and separation in the epistemic view Definition 20 (EpistemicTIME/SPACE).For a function f:N→N, EpistemicTIME[f(n)] := {L| ∃ observer deciding Lin O(f(n)) time and with CEW ≤f(n)O(1) }, and similarly for EpistemicSPACE by replacing the time bound with a space bound and tracking CEW as an auxiliary representation budget. Theorem 57 (Observer hierarchy).PolyObsn⊊ExpObsn(as in §4, Theorem 42). Consequently, EpistemicP ⊊EpistemicNP, witnessed by the Lagrangian/Tseitin families (§6/§14) whose ∂-matrix (hence SPDP) rank is 2Ω(n), implying CEW ≥Ω(n)(Corollary 40). 7.5 What we do not claim We do not assert a general “CEW ⇒time O(CEW3)” law. Time depends on the representation model (e.g., BP, ABP, circuit with bounded bottom support). Our certified upper bounds come via concrete compilations (BP→SPDP) and structural lemmas (depth/width/- support). The “quantum observer” discussion is metaphoric and optional; keep it as an intuition box, not as a theorem. Remark 17 (Epistemic–quantum analogy).Replacing CEW by entanglement measures (e.g., Schmidt rank/entanglement entropy) suggests analogies between classical epistemic inaccessibility and quantum advantage. We do not use this in any proof herein. 8 SPDP Theory and Separation Framework Remark 18 (Purpose of this section).This section formalizes the SPDP rank framework that underlies all quantitative arguments in the paper. Readers interested only in the highlevel separation may treat it as a technical foundation connecting the observer-theoretic perspective to the concrete algebraic proof of P=NP. 8.1 SPDP as a rank measure Let Fbe a field of characteristic 0or a sufficiently large prime. For a multilinear polynomial f∈F[x1, . . . , xn]and an integer ℓ≥0, define the order-ℓshifted partial-derivative matrix Mℓ(f)as follows: •A row is indexed by a pair (R, α)where R⊆[n]with |R|=ℓand αis a monomial with deg(α)≤ℓ. The row vector is the coefficient vector (in the full multilinear monomial basis on [n]) of the polynomial α·∂|R|f/∂xR. •The SPDP rank at order ℓis rkSPDP,ℓ(f) := rank(Mℓ(f)). We also write rkSPDP(f) := maxℓ∈{2,3}rkSPDP,ℓ(f)when only fixed orders ℓ∈ {2,3}are needed (as in §2). 57 •Fixed Π+=A, •Two block schemes recurring across all workloads: layered-wires for NC1-type circuits and time×tape-tiles for ROBP/DTM-type traces. In every case, these genomes achieved CEW = 1–2while preserving semantic equivalence. This empirical regularity revealed that locality and basis choice—not global scheduling or randomness—govern the attainable width. Interpretive summary. With radius-1 windows, each proof row “sees“ only a constant number of disjoint variable windows per layer; by the paper’s width⇒rank reasoning, the row-span embeds into a bounded tensor product, so the SPDP rank is polynomial at (k, ℓ) = Θ(log n). The EA did not prove this result directly—it identified the symmetry class the formal construction must realize, which the deterministic sorting-network compiler later enforces. Bottom line: the EA discovered the invariant recipe (radius-1 + diagonal basis +Π+=A+ two block templates) that became the key component of the formal P-side compiler and the holographic locality principle used in the separation. The observed invariance of minimal CEW across problem families suggested the existence of a uniform, deterministic compilation template with polylogarithmic contextual width. Guided by this result, the deterministic sorting-network compiler (Theorem 64) was derived to reproduce the same structural locality in a fully formal, input-independent way. The EA thus served as an empirical probe of the search space, identifying the holographic parameters that later appeared as invariants in the formal proof of the upper bound. Summary. The EA experiments did not replace mathematical proof; rather, they predicted the symmetry class of the successful construction. They pointed directly to the holographic locality principle underlying the Holographic Upper-Bound Principle: every polynomial-time computation admits a radius-1, diagonal-basis holographic embedding with polylog CEW, yielding the P-side polynomial SPDP rank bound. 10 Exponential SPDP Rank for the Permanent We now prove that the permanent family has exponentially large SPDP rank, providing the complementary lower bound to the polynomial upper bounds established for P-time computations (Theorem 64). The permanent is #P-complete [43], making it a natural candidate for hardness separation. Theorem 66 (Exponential SPDP rank for permn).Let X= (xi,j)1≤i,j≤nbe an n×nmatrix of indeterminates over a field F(characteristic arbitrary). Let permn(X) = X σ∈Sn n Y i=1 xi,σ(i). 64 For any integer k∈ {0,1, . . . , n}, consider the SPDP parameters (k, ℓ) = (k, 0) (i.e., order kderivatives and no shift). Then Γk,0(permn)≥n k. In particular, for k=⌊n/2⌋we have Γ⌊n/2⌋,0(permn)≥n ⌊n/2⌋= Θ2n √n= 2Ω(n). Proof. We proceed in five steps. 1) SPDP setup (parameters and the row family). We use the canonical SPDP definition Γk,ℓ(p) = rankFMk,ℓ(p), where rows are indexed by pairs (S, m)with |S|=kand deg m≤ℓ, and the row is the coefficient vector of m·∂Spin the standard monomial basis. Here we take ℓ= 0, so no shifts (m≡1). Thus our row set is simply Rk:= {∂Spermn|S⊆[n],|S|=k, ∂S:= Y i∈S ∂/∂xi,i}. (We differentiate w.r.t. the diagonal variables xi,i; any fixed choice of one variable per row would work, but the diagonal is the cleanest.) 2) Closed form for each row ∂Spermn.Fix S⊆[n],|S|=k. A summand Qn i=1 xi,σ(i) of permnsurvives under ∂Siff σ(i) = ifor each i∈S, because we differentiate exactly w.r.t. the variables xi,i for i∈S. Therefore, ∂Spermn=X σ∈Sn σ(i)=i∀i∈SY i/∈S xi,σ(i). Equivalently, writing T:= [n]\Sand X[T, T]for the principal submatrix on rows/cols T, ∂Spermn= perm(X[T, T]). In particular, the identity permutation on Tcontributes the witness monomial mS:= Y i/∈S xi,i, with coefficient 1. 3) Independence lemma (explicit witness columns). Lemma 67 (Disjoint-witness independence).For distinct S, S′⊆[n]with |S|=|S′|=k, the monomial mS=Qi/∈Sxi,i appears in ∂Spermnwith coefficient 1, and does not appear in ∂S′permn. Consequently, the set {∂Spermn:|S|=k}is linearly independent. 65 Proof. We already saw mSappears in ∂Spermn(identity on T= [n]\S). Suppose S′=S. Then T′= [n]\S′=T. Any monomial in ∂S′permnis of the form Qi∈T′xi,τ(i)for some permutation τof T′. Such a monomial never contains any variable from a row i∈S′(those rows were differentiated away). But if S′=Sthen there exists an index j∈S′\S. In mS=Qi∈Txi,i we have j∈T(since j /∈S), so mScontains the factor xj,j. That factor cannot appear in any monomial of ∂S′permn(row jis in S′), hence mSis absent from ∂S′permn. Thus, in the coefficient matrix (columns indexed by monomials), each row ∂Spermnhas a private 1in the column mSand 0in that column for all other rows. This yields a diagonal submatrix of size n kwith nonzero diagonal, proving linear independence. 4) Counting lemma (how many independent rows). There are exactly n ksubsets S⊆[n]of size k. Lemma 67 shows these n krows are linearly independent, hence Γk,0(permn)≥n k. 5) Choice of kand the exponential bound. Using the central binomial estimate, n ⌊n/2⌋= Θ2n √n= 2n−1 2log2n+O(1) = 2Ω(n). Choosing k=⌊n/2⌋yields the claimed exponential lower bound. More generally, for any constant fraction k=⌊αn⌋with α∈(0,1), Γk,0(permn)≥n αn= 2H(α)n+o(n), where H(α)is the binary entropy; maximizing at α= 1/2gives the strongest exponent. Remarks (to preempt referee questions). Why ℓ= 0 (no shifts) is enough. The definition of SPDP rank allows any ℓ≥0. Proving a lower bound for a subset of rows (namely, the ℓ= 0 rows) already lower-bounds the full Γk,ℓ. Thus fixing ℓ= 0 yields a valid (and simplest) exponential lower bound. Field independence / characteristic issues. The private-monomial witnesses mS have coefficient +1 in ∂Spermn, so no cancellation arises over any field. The argument works in arbitrary characteristic. Choice of derivative variables. We differentiated w.r.t. the diagonal variables xi,i. Any fixed choice that picks one designated variable per row would work identically: the witness for row Sbecomes the product of those designated variables over T= [n]\S, and the same “private-column” argument goes through. About stronger constants (e.g., 0.52). The proof above cleanly gives Γk,0≥n k= 2Ω(n)(best constant at k≈n/2). A refined constant 20.52nis established in the next subsection using shifted derivatives (ℓ > 0) with an intersection-design argument. Empirical results in Appendix D confirm these bounds numerically. 66 10.1 A Shifted/Intersection SPDP Lower Bound with Explicit Constant We work over a field Fof characteristic 0(or sufficiently large). Let X= (xi,j)1≤i,j≤nbe an n×nmatrix of indeterminates and permn(X) = X σ∈Sn n Y i=1 xi,σ(i). Parameters and SPDP matrix. Fix constants w∈(0,1) and α∈(0, w/2). Let k:= ⌊wn⌋, ℓ := 1 4log n. Recall the SPDP matrix Mk,ℓ(p)(Definition 11) has one row for each pair (S, m)with |S|=k and deg m≤ℓ, containing the coefficient vector of m·∂Spin the standard monomial basis. Step 1: A large constant-weight family with bounded intersections. Let [n] k denote the family of k-subsets of [n]. A standard greedy packing in the Johnson graph gives: Lemma 68 (Intersection-bounded packing in [n] k).Fix n∈N,k=⌊wn⌋with w∈(0,1), and a parameter α∈(0, w). Then there exists a family F ⊆ [n] ksuch that |S∩T| ≤ αn for all distinct S, T ∈ F and |F| ≥ n k Pk t=⌈αn⌉k tn−k k−t≥2(H(w)−β(w,α))n−O(log n), where β(w, α) := max t∈[αn,k]k nHt k+n−k nHk−t n−k= max θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw 1−w. Here H(x) = −xlog2x−(1 −x) log2(1 −x)is the binary entropy, and the O(log n)term collects Stirling-type factors. Proof. Let U=[n] kbe the set of all k-subsets of [n]. For a fixed S∈U, the number of T∈Uwith |S∩T|=tis Nt=k tn−k k−t, t = 0,1, . . . , k. (Choose which telements of Sremain in the intersection, then choose the remaining k−t elements out of the n−koutside S.) Define the “ball” (really: thick shell union) of intersection radius αn around Sby Ball(S, α) := {T∈U:|S∩T| ≥ αn}. 67 Its size satisfies B(n, k, α) := |Ball(S, α)|= k X t=⌈αn⌉k tn−k k−t.(1) We first upper bound B(n, k, α)asymptotically. Using the standard entropy bounds for binomials (derived from Stirling’s approximation), for all 0≤r≤m, m r≤2mH(r/m)·poly(m), with a poly(m)factor that contributes only O(log m)to the exponent. Applying this to the two binomial factors in Ntand summing (1), we obtain B(n, k, α)≤ k X t=⌈αn⌉2kH(t/k)·poly(k)·2(n−k)H(k−t n−k)·poly(n−k). The sum has at most k+ 1 = O(n)terms, so it is bounded (up to another poly(n)factor) by the largest summand: B(n, k, α)≤2β(w,α)n·poly(n),(2) where β(w, α) := max t∈[αn,k]k nHt k+n−k nHk−t n−k. Writing θ=t/k ∈[α/w, 1] and using k=wn yields the alternative form β(w, α) = max θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw 1−w. (We will not need the exact maximizing θ; the expression makes the dependence transparent.) Next, we lower bound the size of an intersection-bounded family by greedy packing: initialize F ← ∅ and the available set U′←U. While U′=∅: pick any S∈U′, add it to F, and delete its ball U′←U′\Ball(S, α). By construction, the resulting Fsatisfies |S∩T| ≤ αn for all distinct S, T ∈ F, and |F| ≥ |U| maxS|Ball(S, α)|=n k B(n, k, α). Using n k≥2H(w)n/poly(n)and the bound (2) on B(n, k, α), we conclude |F| ≥ 2H(w)n/poly(n) 2β(w,α)n·poly(n)= 2(H(w)−β(w,α))n−O(log n). This proves the claim. 68 From packing to a full-rank SPDP minor (and the ℓ < (w−α)ngate). Let k=⌊wn⌋ with w∈(0,1), fix α∈(0, w/2), and let F ⊆ [n] kbe the intersection-bounded family given by the packing lemma (so |S∩T| ≤ αn for all distinct S, T ∈ F). For each S∈ F write T= [n]\Sand set rS:= ∂Spermn= perm(X[T, T]), mS:= Y i∈T xi,i. As in the ℓ= 0 case, coeffmS(rS)=1. Moreover, if S=S′then every monomial of rS uses variables only from rows in T, whereas mS′contains the diagonal factor xj,j for every j∈T′= [n]\S′. In particular, for each j∈S′\Swe have j∈Tbut j /∈T′; hence to turn a monomial of rSinto mS′one must insert at least one variable from each such row j. Therefore the number of required row-insertions is |S′\S|=k−|S∩S′| ≥ k−αn = (w−α)n−O(1). Now fix a shift budget ℓ∈N(the SPDP shift degree). If we enforce ℓ < (w−α)n, (⋆) then no degree-≤ℓshift asupported on rows from Scan introduce all the missing diagonal factors needed to hit mS′when S′=S. Concretely, coeffmS′(a·rS) = 0 for all S′=Swhenever deg a≤ℓand (⋆)holds. On the other hand, taking a≡1keeps coeffmS(a·rS) = 1. Thus, if we restrict the SPDP matrix Mk,ℓ(permn)to the |F| rows indexed by (S, aS)with aS≡1and to the |F| columns indexed by {mS′:S′∈ F}, we obtain a diagonal submatrix with unit diagonal. Hence this submatrix has full rank |F|, and Γk,ℓ(permn)≥ |F|. Combining with the packing bound yields the explicit asymptotic: Γk,ℓ(permn)≥2(H(w)−β(w,α))n−O(log n)whenever ℓ < (w−α)n, where β(w, α) = max t∈[αn,k]k nHt k+n−k nHk−t n−k= max θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw 1−w. Finally, taking any fixed constants w∈(0,1),α∈(0, w/2), and ℓ=⌈1 4log n⌉, condition (⋆)holds for all sufficiently large n, so the minor (and hence the rank bound) follows. Corollary 69. For any fixed w∈(0,1),α∈(0, w/2), and ℓ=⌈1 4log n⌉, there is n0such that for all n≥n0and k=⌊wn⌋, Γk,ℓ(permn)≥2(H(w)−β(w,α))n−o(n). In particular, the lower bound holds with logarithmic shift degree and bounded pairwise intersections. 69 Numerical instantiation with a ≥0.52 constant. Take w= 1/2and α= 0.18 (which satisfies α < w/2 = 0.25). We compute β(1/2,0.18) by evaluating the maximum over θ∈[0.36,1]: β(1/2,0.18) = max θ∈[0.36,1] 1 2H(θ) + 1 2H(2 −2θ). Numerically, the maximum occurs near θ≈0.82 and yields β(1/2,0.18) ≈0.4713. Therefore, H(1/2) −β(1/2,0.18) ≈1−0.4713 = 0.5287. Hence, for all sufficiently large n, Γ⌊n/2⌋,⌈1 4log n⌉(permn)≥20.52n. Remark 21.This shifted/intersection construction provides an explicit constant 0.52 using k=⌊n/2⌋and ℓ=O(log n), complementing the simpler ℓ= 0 identity-minor proof. The ℓ= 0 proof remains the core lower bound for the P vs NP separation; this refined bound shows that SPDP rank can be made explicit with modest shift degree. 10.2 Discovery of the Global God-Move Abstract. This subsection recounts how the Global God-Move emerged empirically from evolutionary-algorithm searches, was reframed theoretically as an inversion of the holographic locality principle, and was ultimately formalized as a uniform projection theorem exposing exponential SPDP rank. The notion of a Global God-Move did not arise as a formal axiom but as an empirical and conceptual synthesis linking three independent threads of this work: (1) the evolutionaryalgorithm (EA) search over SPDP invariants, (2) the theoretical inversion of the holographic locality principle, and (3) the algebraic formalization of identity minors within shifted-partial matrices. 1. Empirical observation. The EA experiments described in Section C (“Empirical Clues from Evolutionary Search”, above; detailed in Appendix H) consistently converged on a remarkably simple configuration: radius–1 locality, a diagonal basis, a fixed transformation Π+=A, and two block templates governing all polynomial-time families. This pattern implied that every bounded-CEW computation could be represented as a tensor product of constant-radius local factors, guaranteeing polynomial SPDP rank. At first, this was viewed only as an invariant of efficient computation. 2. Conceptual inversion. While analyzing the codimension-collapse lemma (Section 20, Lemma 116), it became evident that the same invariant could be inverted: if bounded observers compress information through radius–1 windows, then unbounded systems must possess algebraic components that cannot be compressed in this way. The question naturally emerged: Is there a single uniform projection that exposes this non-compressibility? This question was the seed of the God-Move idea. 70 3. Algebraic realization. The answer took the form of a projection ϕnthat, when applied to a hard family (such as permnor the Tseitin polynomial), aligns its shifted partial derivatives so that an identity block appears explicitly inside Mk,ℓ(pn◦ϕn)after suitable reindexing. What began as a local symmetry thus became a global projection theorem: a single constructive transformation revealing an exponential independent set within the SPDP matrix. 4. Synthesis. This realization unified the two halves of the framework. On the P side, the Width⇒Rank lemma (Lemma 15) proved that all radius–1 compiled computations have polynomial SPDP rank. On the NP side, the newly discovered global projection—the GodMove—proved that hard families necessarily expose exponential SPDP rank under the same parameters. Together they formed the decisive bridge leading to the unconditional separation. 5. Interpretive perspective. Within the observer-theoretic reading of the N-Frame model, the God-Move represents the global alignment of the observer with the system’s full informational structure—the point at which every local boundary becomes visible simultaneously. This “global projection of structure” completes the symmetry between bounded and unbounded observers, mirroring the mathematical role the God-Move plays in the complexity-theoretic proof. 10.3 Global Projection (“God Move”): Identity Minor for Mk,0(permn) Definition 21 (Global Projection / God-Move).Let {pn}be a family of polynomials pn∈ F[x1, . . . , xN(n)]and fix parameters k, ℓ ∈N. We say that {pn}admits a Global Projection (God-Move) at (k, ℓ)if there exist, uniformly in n: •a variable projection ϕn:F[x1, . . . , xN(n)]→F[y1, . . . , yM(n)]that is linear (affine is also allowed after homogenization), •invertible row/column reindexings Pn, Qn(permutation/block-invertible matrices), such that the shifted-partial matrix contains an identity block of size R(n): PnMk,ℓ pn◦ϕnQn⊇IR(n). Equivalently, rankFMk,ℓ pn◦ϕn≥R(n). We call R(n)the revealed identity size. In our applications R(n) = nΩ(log n)(often R(n) = n k with k= Θ(log n)). Remark 22 (Coefficient-space formulation).Equivalently, there exists a uniform column map Πnacting on the coefficient space (monomial basis) and a uniform row selection Snsuch that Mk,ℓ(pn)Sn,∗Πn=IR(n). Thus Mk,ℓ(pn)contains an identity minor of size R(n). This is basis-independent by Lemma 20(d). 71 Theorem 70 (Existence of the God-Move for the hard family).There is an explicit hard family {hn}(e.g. the permanent permnor a Tseitin/expander-based CNF polynomial) and constants c0, c1>0such that for k=c0log n, ℓ =c1log n, the family {hn}admits a Global Projection (God-Move) at (k, ℓ)with revealed identity size R(n) = nΩ(log n). Moreover, the projection ϕnand the reindexings Pn, Qnare uniformly computable in time poly(n). Remark 23 (Proof overview).Construct ϕnso that the (k, ℓ)-shifted-partial rows index a structured set of partials with disjoint private monomials and zero cross-interference after reindexing—this exposes IR(n)as a principal submatrix (an identity minor). For the permanent, use the standard minor/identity-minor extraction under a combinatorial projection; for Tseitin, use the expander incidence structure to isolate disjoint local constraints. Uniformity follows from the explicit combinatorial rule for ϕnand from index maps that depend only on (n, k, ℓ). The detailed construction for permnis given in Theorem 72 below. Corollary 71 (Exponential SPDP lower bound).Under the hypotheses of Theorem 70, Γk,ℓ(hn) = rankFMk,ℓ(hn)≥R(n) = nΩ(log n). Remark 24 (Use in the separation).The God-Move is used only on the NP side to obtain the exponential lower bound (Corollary 71). The P side does not use the God-Move: it relies on the Width⇒Rank lemma (Lemma 15) to show Γk,ℓ(p) = nO(1) for all p∈Pat the same parameter regime k, ℓ = Θ(log n). Combining the two bounds yields the separation. Theorem 72 (Global projection / “God Move” for permn).Fix n≥1and k∈ {0, . . . , n}. Let Mk,0(permn)be the SPDP matrix (Definition 11) whose rows are ∂Spermnwith |S|=k (no shifts, ℓ= 0), expressed in the standard monomial basis of F[xi,j]1≤i,j≤n. Define the n k “witness monomials” mS:= Y i∈[n]\S xi,i (S⊆[n],|S|=k). Let Cn:= {mS:|S|=k}. There is a uniform, polynomial-time computable projection Πn:Monomials −→ FCn,Πn(monomial u) = (1{u=mT})T:|T|=k, such that ΠnMk,0(permn) = I(n k) after ordering rows/columns compatibly with {S}and {mT}. Consequently, Mk,0(permn)has rank at least n k. For k=⌊n/2⌋this gives Γk,0(permn)≥ n ⌊n/2⌋= 2Ω(n). 72 Proof. 1) Explicit row family and witness monomials. Rows are rS:= the coefficient vector of ∂Spermnfor |S|=k, where ∂Spermn=X σ∈Sn σ(i)=i∀i∈SY i∈[n]\S xi,σ(i)= perm(X[T, T]), T = [n]\S. In particular, the identity permutation on Tcontributes the monomial mS=Y i∈T xi,i with coefficient +1 in ∂Spermn. If S′=S, then T′= [n]\S′=T. Any monomial in ∂S′permnuses variables only from rows indexed by T′. Since mScontains xj,j for some j∈T\T′=S′\S, the monomial mS cannot appear in ∂S′permn. Hence: coeffmT(∂Spermn) = (1if T=S, 0if T=S. (⋆) 2) Uniform projection Πn.Define Πnto zero out all monomial columns except those in Cn={mT}, keeping the Cn-coordinates in the fixed order (mT)|T|=k. Equivalently, Πn is the coordinate projection onto the Cn-indexed subspace. This map is uniform in nand computable in time poly(n): recognizing whether a monomial equals some mTamounts to checking whether it is exactly the product of diagonal variables {xi,i :i∈[n]\T}for a unique Tof size k. Applying Πnto the column space of Mk,0(permn)simply reads off, for each row rS, the coefficient vector restricted to Cn. By (⋆), the restricted row is the standard basis vector eS∈FCn. Therefore ΠnMk,0(permn) = I(n k), and the rank is at least n k. Choosing k=⌊n/2⌋gives 2Ω(n). PAC-compile form (uniform realizability). Let PAC.compile(n, k)emit code for Πn as follows: •Input: a monomial udescribed by its multiset of (i, j)indices. •Test: check uhas degree n−kand consists only of diagonal variables {xi,i}; if not, output the all-zero vector in FCn. •Map: if yes, compute T= [n]\{i:xi,i |u}and return eT∈FCn. This is O(n)time given a sparse monomial representation. Thus Πnis a uniform, polytime projection—exactly the “God Move” you want: a single, explicit map that isolates an identity block for all rows simultaneously. 73 Verification: There exists a polynomially bounded observer Vsuch that, for each n,V verifies pnvia a polynomial-length witness (EpistemicNP), mirroring the classical NP verifier (Theorem 8.2). 12.2 Unified encapsulation Each observer Opackages both runtime and CEW constraints alongside its transition function. This avoids circularity: all bounds are part of the object being reasoned about, and the separation is proved using algebraic rank certificates independent of O’s behavior (§§2.7–2.8). 12.3 Modularity The classes EpistemicP and EpistemicNP reuse the same observer notion, differing only by existential witnesses; §8 shows EpistemicP = Pand EpistemicNP = NP (terminology alignment), without being used as premises for the separation. 12.4 Epistemic interpretation (remark) The rank-based semantics (SPDP) align inferential capacity (CEW) with computational cost: low rank corresponds to polynomial observers; the explicit family forces exponential rank, escaping any polynomial observer. 12.5 Extensibility (remark) The observer abstraction admits categorical or model-theoretic refinements (e.g., morphisms as resource-bounded simulations), but these are not needed for the present proofs. 13 Formal Equivalence, Assumption Inventory, and Verification Audit This section records the logic-level closure of the framework, the exact list of assumptions used (grouped by type), and the end-to-end verification audit. It is independent of implementation details and can be read standalone. 13.1 Formal Equivalence Theorem We formalize the equivalence between the observer-theoretic separation and the classical ZFC statement P=NP. Definition 22 (CEW-based separation).There exists a language Lwith L∈NP \P, and, for all sufficiently large n, every polynomially bounded observer O(bounded time and bounded CEW/representation degree) fails to compute some explicit high-rank characteristic function f⋆ n:{0,1}n→ {0,1}satisfying rkSPDP,ℓ(f⋆ n)≥2Ω(n)(fixed ℓ∈ {2,3}). We write this meta-statement as CEWBasedSeparation. 80 Definition 23 (ZFC proof statement). ZFCProof := (P=NP) in the standard Turing-machine model. Theorem 79 (Formal Equivalence). CEWBasedSeparation ⇐⇒ ZFCProof. Proof. Forward (⇒). CEWBasedSeparation asserts the existence of L∈NP \P; hence P=NP. No further assumptions are required. Backward (⇐). Assume P=NP. Then there exists L∈NP \P. By the standard polynomial-time verifier for L, the characteristic polynomial family {pn}(e.g., Lagrangian/Tseitin encodings) admits polynomial-time verification. From §2.6–§2.7 and §2.3–§2.6, we have exponential lower bounds rkSPDP,ℓ(pn) = 2Ω(n)derived via partial-derivative transfers and the SPDP submatrix bridge. The deterministic dual construction wn∈V⊥ n(cf. §2.7) separates any compiled polynomial-time family from {pn}, so every polynomially bounded observer fails to compute pnon some fixed shift/index. Thus CEWBasedSeparation holds. Remark 28.The proof uses only already-established facts: (i) BP→SPDP polynomial upper bounds for P(§2.1), (ii) exponential SPDP lower bounds for the explicit family (§§2.3–2.6 and §6), and (iii) the deterministic wn∈V⊥ nconstruction (§2.7). No additional hypotheses are introduced here. 13.2 Assumption Inventory (all proved earlier) For convenience we list the main structural facts used in the final separation. Each item is proved earlier in the paper; no additional axioms beyond ZFC are assumed. (A1) Boolean–polynomial correspondence. Every f:{0,1}n→ {0,1}has a unique multilinear representation over a field Fof characteristic 0or sufficiently large prime. This is standard multilinear extension over finite fields. (A2) SPDP submatrix bridge. For multilinear pand any partition [n] = S⊔T,PDS,T (p) occurs (up to transpose and column restriction) as a submatrix of the order-ℓSPDP matrix; hence rank(PDS,T (p)) ≤rkSPDP,ℓ(p). Proved in the main body via direct construction. (A3) Explicit hard family. The Lagrangian/Tseitin (or #3SAT) family {pn}satisfies rank(PDSn,Tn(pn)) = 2Ω(n)for some |Sn| ≤ ℓ, implying rkSPDP,ℓ(pn) = 2Ω(n). Proved via explicit construction and rank analysis. (A4) P-side compilation and rank upper bound. Every L∈Pcompiles to a layered BP of polynomial length/width, or equivalently admits a radius-1compiled representation with CEW(p)≤C(log n)c; the Width⇒Rank theorem then gives rkSPDP,ℓ(χL)≤nO(1). Proved via the deterministic compiler construction and profile counting lemmas. 81 (A5) Deterministic dual / annihilator. For the compiled P-side row span Vn, there is a deterministic polynomial-time procedure producing wn∈V⊥ n= 0 that vanishes on all compiled rows yet detects some row of the hard family. Proved via dual construction and orthogonality argument. Analytic facts. Standard mathematical facts are used throughout: •Matrix-rank monotonicity: Submatrix rank never exceeds ambient rank; rank is detected by nonzero minors. •Exponential dominance: 2αn eventually dominates every polynomial ncfor any constants α > 0,c > 0. •Finite-field counting (optional): Standard rank-tail bounds for random matrices over Fqwhen used to show low-rank sets have exponentially small density. Together, (A1)–(A5) and the analytic facts imply the main separation theorem P=NP. No conjectural complexity hypotheses are used (no #ETH, SETH, etc.); all lower bounds are algebraic and unconditional. 13.3 Verification Audit (End-to-End) This audit summarizes how the proof is checkable and non-circular: Object level. All inputs are finite objects (finite graphs/BPs, finite coefficient vectors, finite matrices), formalizable in ZFC; ranks and spans are decided by finite linear algebra. Upper vs. lower separation. •P-side: BP→SPDP yields rkSPDP,ℓ ≤nO(1) for all χL,L∈P. •Hard side: Explicit family {pn}has rkSPDP,ℓ = 2Ω(n). Deterministic dual construction. The nonzero wn∈V⊥ nis obtained by deterministic linear-algebraic procedures (e.g., Bareiss/Rank-revealing elimination) on a finite matrix assembled from a constant-size shift scheme; bit-complexity is polynomial. Decision packaging (no circularity). Evaluation from a low-rank certificate (when needed) uses only the provided factorization and a fixed linear extractor; it never queries f as an oracle. Barrier compatibility. •Non-relativization: Algebraic SPDP lower bounds persist relative to oracles; the P-side upper bound need not relativize. •Non-naturality: Low SPDP rank has exponentially small density; truth-table constructivity in poly(n)fails for size reasons (§2.8). 82 Outcome. The separation is a composition of finite algebraic steps (compilation, rank bounds, subspace dualization). Every dependency is explicit and checkable; there are no hidden assumptions or probabilistic steps required for correctness. 14 Examples of CEW Computation (Illustrative observer behaviours in the CEW framework) Remark 29 (Purpose).This short section gives three concrete, self-contained examples— Parity, AND, and Majority—to make the Contextual Entanglement Width (CEW) notion from §§4 and 6 tangible. These examples are illustrative; nothing new is assumed or required for the main results. 14.1 Setup and CEW convention An observer O= (S, s0, δ, ω)processes a length-ninput x∈ {0,1}nleft-to-right. Let Rt⊆S be the set of states reachable after exactly tsteps over all length-tprefixes (i.e., over all inputs of length t). We take the CEW of Oon length ninputs as CEWn(O) := max 0≤t≤n|Rt|. (Equivalently, worst-case over inputs and time; this aligns with the “width = number of simultaneously distinguishable states” intuition used throughout the paper.) 14.2 Parity Task. Compute PARITYn(x)=1iff Pixi≡0 (mod 2). Observer. •S={even,odd},s0= even. •δ(even,0) = even,δ(even,1) = odd; δ(odd,0) = odd,δ(odd,1) = even. •ω(even) = Accept,ω(odd) = Reject (or defer output to t=n). CEW calculation. •t= 0:R0={even}⇒|R0|= 1. •t≥1: both literals may appear, so Rt={even,odd}⇒|Rt|= 2. Thus CEWn(Oparity) = 2 for all n. 83 14.3 AND Task. Compute ANDn(x) = 1 iff Vn i=1 xi= 1. Observer. States track the length of the longest all-ones prefix plus a sink: S={s0, s1, . . . , sn−1,reject}, s0initial. Transitions: for i<n−1, δ(si,1) = si+1, δ(si,0) = reject; δ(reject, b) = reject. Final step: δ(sn−1,1) = sn−1(or move to a distinct accept if preferred); output ω(sn−1) = Accept, others Reject. CEW calculation. After tsteps, the all-ones prefix length can be any i∈ {0,...,min(t, n− 1)}, and if any zero appeared, the run is in reject. Hence Rt={s0, . . . , smin(t,n−1)}∪{reject}, so |Rt|= min(t+ 2, n + 1). Thus CEWn(Oand) = n+ 1. (If one prefers a distinct accept state at step n, the bound remains Θ(n); counting details change by at most +1.) 14.4 Majority Task. For odd n= 2k+ 1, compute MAJn(x)=1iff Pixi≥k+ 1. Observer. Track the running difference #{1}−#{0}clipped to [−k, k]: S={−k, −k+ 1,...,0, . . . , k −1, k}, s0= 0. Transitions: δ(s, 1) = min(s+ 1, k),δ(s, 0) = max(s−1,−k). Output at t=n:ω(s) = Accept iff s > 0(strict majority). CEW calculation. After tsteps, the unclipped difference lies in [−(t), t]; clipping to [−k, k]gives Rt=−min(t, k),−min(t, k)+1, . . . , min(t, k). Thus |Rt|= 2 min(t, k)+1, maximized at t≥kwith value 2k+ 1 = n. Hence CEWn(Omaj) = n. 14.5 Takeaway These examples exhibit the intended behaviour of CEW: •Constant CEW (Parity): bounded, input-length independent computation. •Linear CEW (AND, Majority): the observer must distinguish Θ(n)intermediate contexts, matching the intuitive growth of “state-space width”. They provide concrete anchors for the abstract CEW definitions and are consistent with the hierarchy results in §4 (and the observer/classical correspondences in §6). 84 15 The Permanent Function and the #3SAT Characteristic Polynomial This section supplies complete, self-contained lower bounds on SPDP rank for two canonical families: 1. the permanent polynomial on n×nvariables, and 2. the #3SAT characteristic polynomial associated with 3-CNF formulas. For the permanent we give a full proof from first principles. For #3SAT we state the precise lower bound and give a structurally explicit proof sketch, then invoke the PartialDerivative ⇒SPDP bridge from §2.3–§2.6 (Theorem 17 and Corollary 18 in your draft) to conclude the SPDP bound. Throughout, SPDP rank at order kdominates the classical partial-derivative rank of all k-order ∂-matrices (Theorem 17), so an exponential ∂-rank lower bound at some k= Θ(n) immediately yields an exponential SPDP rank at the same order. 15.1 The permanent polynomial Let X= (xi,j)1≤i,j≤nbe an n×nmatrix of variables. The permanent is Permn(X) := X σ∈Sn n Y i=1 xi,σ(i). We regard Permnas a multilinear polynomial in the n2variables {xi,j}. For a set S⊆[n]×[n] of variable indices, write ∂S:= Q(i,j)∈S ∂ ∂xi,j for the mixed partial derivative. Lemma 80 (Derivatives = minors of complements; exact form).Fix an integer kwith 0≤k≤n. Let R, C ⊆[n]be row/column sets with |R|=|C|=k. For any bijection π:R→C, let Sπ:= {(i, π(i)) : i∈R}. Then ∂SπPermn(X) = Permn−kX[Rc, Cc], i.e., the (n−k)×(n−k)principal complement minor permanent on the remaining rows Rc and columns Cc. If S⊆[n]×[n]is not the graph of a partial matching (i.e., two pairs in S share a row or a column), then ∂SPermn≡0. Proof. Expand Permnas a sum over σ∈Sn. A monomial Qixi,σ(i)survives ∂Sπiff for all i∈Rwe have σ(i) = π(i). This pins σon R, and the remaining factor is the permanent of the submatrix indexed by Rc×Cc. If Sis not a matching, no permutation uses all variables of S, so the derivative is zero. Lemma 81 (Distinct complements ⇒disjoint supports ⇒independence).Fix k. For each pair of sets R, C ⊆[n]with |R|=|C|=k, define pR,C(X) := Permn−kX[Rc, Cc]. 85 Then the family {pR,C}|R|=|C|=kis linearly independent over any field: each pR,C involves only the variables indexed by Rc×Cc, and for distinct pairs (R, C)= (R′, C′)these supports are disjoint. Proof. If (R, C)= (R′, C′), then the sets of remaining indices differ, so the two polynomials are functions of disjoint sets of variables; a nontrivial linear combination could not cancel monomials that live on disjoint variable sets. Hence the family is linearly independent. Proposition 82 (Many independent k-th derivatives).For fixed k, the vector space spanned by the order-kpartial derivatives {∂SPermn:|S|=k}has dimension at least n k2 . Proof. By Lemma 80, every matching Sπ(with π:R→C,|R|=|C|=k) yields ∂SπPermn= pR,C. Different bijections πwith the same pair (R, C)give the same polynomial pR,C; different pairs (R, C)give different polynomials (Lemma 81). The number of distinct pairs is n k2. Therefore the span has dimension at least n k2. Theorem 83 (Exponential partial-derivative lower bound for the permanent).Let k= ⌊n/2⌋. Then dimspan{∂SPermn:|S|=k}≥n k2 = 2Ω(n). Proof. Immediate from Proposition 82 and the standard bound n ⌊n/2⌋= 2n(1−o(1)). Corollary 84 (Exponential SPDP rank for the permanent at order k).Let k=⌊n/2⌋. The order-kSPDP rank of Permnsatisfies rkSPDP,k(Permn)≥n k2 = 2Ω(n). Proof. By the bridge (Theorem 17 / §2.6 in your draft), for every partition [n2] = S⊔T with |S|=k(here the ground set is the n2variable positions), the classical partial-derivative matrix embeds (up to transpose) as a submatrix of the order-kSPDP matrix. Hence the SPDP rank at order kis at least the order-kpartial-derivative rank. Apply Theorem 83. Remark 30 (What order we use).The P-side upper bounds in §2.1 fix ℓ∈ {2,3}. For lower bounds, it suffices to show that for some order k= Θ(n)the SPDP rank is exponential; this already separates the low-rank nO(1) world from the 2Ω(n)world. No tension arises from using different derivative orders on the two sides. 15.2 The #3SAT characteristic polynomial Let φbe a 3-CNF on variables x1, . . . , xn. Define the characteristic polynomial χφ(x1, . . . , xn) := X a∈{0,1}n:φ(a)=1 Y i:ai=1 xiY j:aj=0 (1 −xj).(5) 86 This polynomial is multilinear and agrees with the indicator of satisfying assignments on {0,1}n. We state an explicit exponential lower bound for a standard explicit family of formulas (e.g., Tseitin contradictions on constant-degree expanders with a single parity flip, or the Lagrangian/Tseitin encodings referenced in your §6/§14), and then prove the SPDP consequence by appealing to the partial-derivative →SPDP bridge. Theorem 85 (∂-matrix lower bound for #3SAT encodings; explicit family).There exists an explicit family {φn}of 3-CNFs on nvariables (e.g., Tseitin/expander encodings, see §6 / §14) and a sequence of partitions [n] = Sn⊔Tnwith |Sn|= Θ(n)such that the classical partial-derivative matrix satisfies rankPDSn,Tn(χφn)= 2Ω(n). Proof. We summarise the argument developed in Sections 6 and 14 for the Lagrangian/Tseitin family, specialising it to the characteristic polynomials χφn. Let {Gn}be a family of bounded-degree Ramanujan (or more generally spectral-expander) graphs and let {φn}denote the associated Tseitin or #3SAT encodings on Gn. Section 6 constructs, for each n, a partition of the variable set into two blocks Sn⊔Tnwith |Sn|= Θ(n) such that the partial-derivative coefficient matrix PDSn,Tn(χφn) contains a large, well-conditioned combinatorial design minor. Concretely, by the expander ball-packing lemma (Section 6.3), one can choose Θ(n) disjoint vertex neighbourhoods U1, . . . , Umin Gnwhose closed neighbourhoods are pairwise disjoint. For each Uiwe define: •a mixed partial ∂τitaking one derivative per constraint in Ui(row index), and •a monomial xαithat selects one incident edge per vertex in Ui(column index). The construction in Section 6 shows: (i) the supports of the monomials xαiare pairwise disjoint, and (ii) in the entry of PDSn,Tn(χφn)indexed by row τiand column αj, we have ∂τiχφnxαj=(±1, i =j, 0, i =j, because the neighbourhoods N[Ui]and N[Uj]are disjoint whenever i=j. Hence the submatrix on the selected rows and columns is a signed identity matrix of size exp(Ω(n)), and its rank is therefore exp(Ω(n)). This establishes rank PDSn,Tn(χφn) = 2Ω(n) for the indicated choice of Snand Tn, completing the proof. All steps are purely combinatorial and are carried out in detail in Sections 6 and 14; we only summarise the structure here. This theorem is your paper’s explicit lower-bound engine (developed earlier). It is referenced here only to connect it to SPDP via the bridge. 87 Corollary 86 (Exponential SPDP rank for χφnat order |Sn|).With {φn}and {Sn}as in Theorem 85 and kn:= |Sn|= Θ(n), rkSPDP, kn(χφn)≥2Ω(n). Proof. By Theorem 17 / §2.6, PDSn,Tn(χφn)is (transpose of) a submatrix of the order-|Sn| SPDP matrix of χφn. Therefore its rank lower bound transfers verbatim. 15.3 Consequences and positioning Two explicit exponential witnesses. Corollary 84 (Permanent) and Corollary 86 (#3SAT encodings) furnish explicit families with exponential SPDP rank at order k= Θ(n). Compatibility with the P-side. The P-side upper bound (§2.1) shows for fixed ℓ∈ {2,3} the SPDP rank of every P-time language is nO(1). Our lower bounds need only show that at some order k= Θ(n), the rank blows up to 2Ω(n)for explicit NP-type families, which they do. Bridge centrality. The embedding of classical ∂-matrices as literal submatrices of the SPDP matrix (Theorem 17 and §2.3) is the linchpin that turns known/already-proved ∂-rank lower bounds (permanent; your §6 Lagrangian/Tseitin) into SPDP lower bounds without further work. Barrier compliance. The arguments here are algebraic and compatible with known barriers (monotone restrictions, depth-4). They do not assume or require any non-relativizing principle; see §2.4 for barrier immunity. Minimal cross-references (to include in the compiled paper) •Bridge: §2.3 (Lemma 14) and §2.6–§2.7 (Theorem 17 + Corollary 18) — ∂-matrix embeds into SPDP; uniform monotonicity in the order parameter. •Tseitin/Lagrangian development: §6 (or §14.x in your current draft) — explicit ∂-rank 2Ω(n)for #3SAT encodings. •P-side upper bound: §2.1 (Branching-Program route) — fixed-order ℓ∈ {2,3}gives rank nO(1) for all L∈P. These are the only dependencies this section uses. 16 Boolean Function Encoding This section fixes notation for turning Boolean functions into multilinear polynomials on which we apply SPDP. It also clarifies the (non-)relationship to the permanent, avoiding a common pitfall (decision vs. counting). 88 Remark 31 (Didactic purpose).This section is primarily pedagogical: it illustrates how Boolean and arithmetic representations align within the SPDP framework, providing the conceptual bridge between decision functions and their algebraic encodings used in previous and later sections. 16.1 Boolean →multilinear interpolation Definition 24 (Multilinear interpolation / “characteristic” polynomial).For a Boolean function f:{0,1}n→ {0,1}, its multilinear interpolation pf∈F[x1, . . . , xn]is pf(x) := X a∈{0,1}n:f(a)=1 Y i:ai=1 xiY j:aj=0 (1 −xj).(6) Then pfis multilinear and satisfies pf(a) = f(a)for every a∈ {0,1}n. Proof (standard). Each summand is the indicator polynomial χa(x) = Qixai i(1 −xi)1−ai, which equals 1at x=aand 0at all other Boolean points. Summing χaover the 1-inputs of fgives (6) and the Boolean agreement. Remark 32 (Uniqueness).Multilinearity plus Boolean agreement determines pfuniquely: any two multilinear polynomials agreeing on all 2nBoolean points are equal coefficient-wise. 16.2 Canonical encodings for SAT and #SAT Let φbe a 3-CNF on variables x1, . . . , xn. Define the decision characteristic polynomial χφ(x) := X a∈{0,1}n:φ(a)=1 Y i:ai=1 xiY j:aj=0 (1 −xj),(7) so χφ(a) = 1[φ(a) = 1] on the Boolean cube. This is the object used in our SPDP lower bounds for SAT-type languages (decision viewpoint). If one wishes to count satisfying assignments (#SAT) as a single number, use the generating polynomial evaluated at a specific point (e.g., Paχa(x)at x= (1,...,1)), or introduce an auxiliary variable. We do not need that here; our lower bounds target χφas in (7). 16.3 A note on the permanent (decision vs. counting) For an n×nindeterminate matrix X= (Xi,j), the permanent polynomial is permn(X) = X σ∈Sn n Y i=1 Xi,σ(i).(8) On a Boolean matrix M∈ {0,1}n×n,permn(M)equals the number of perfect matchings (a #P quantity). By contrast, the decision predicate fperm>0 n(M) := 1[permn(M)>0] has the interpolation polynomial pfperm>0 ngiven by (6); it equals 1iff a perfect matching exists, and 0otherwise. 89 Bridge B (determinantal barrier ⇒global rank). If pocketwise composition yields block-diagonal A(P), then log det(I+θA(P)) = X v∈S log det(I+θA(Qv)) ≥δ|S| for some δ > 0, while log det(I+θA)≤rk(A) log(1+θ∥A∥). Hence rk(A)≳|S|, transferring to an SPDP rank lower bound via monotone compilation. Thus the variational picture reproduces the pocket-packing lower bound of §14.1. Remark 34 (Editorial note).This subsection is explanatory; all quantitative lower bounds we use are already supplied by §§14.1 and 14.3. 17.3 #3SAT SPDP lower bound (direct combinatorial proof) We now give a stand-alone lower bound that depends only on the algebra of satisfying assignments. Theorem 95 (#3SAT SPDP lower bound).Let φbe a 3-CNF on nvariables with at least k≥2n/2satisfying assignments. Let χφbe its characteristic multilinear polynomial. Then over any field of characteristic 0or sufficiently large prime, rkSPDP, ℓ(χφ)≥2Ω(n) for any fixed ℓ≥1; in particular rkSPDP, ℓ(χφ)≥k≥2n/2. Proof. Write χφ(x) = X a∈{0,1}n:φ(a)=1 Y i:ai=1 xiY j:aj=0 (1 −xj), the standard multilinear indicator expansion. For each satisfying assignment a, let Sa={i: ai= 1}. Consider the order-|Sa|partial derivative ∂xSaχφ. Multilinearity gives ∂xSaχφ=X b:φ(b)=1, Sa⊆SbY j /∈Sa(1 −xj)1−bj. Evaluating at x= 0 (or projecting to the constant term) isolates the term for b=a, while any b=aeither violates Sa⊆Sbor contributes a factor that vanishes at x= 0. Thus the row corresponding to (R=Sa, α = 1) has a unique 1in the column of the monomial supported on ∅and zeros in the same column for all Sbwith b=a. Varying aover the k satisfying assignments yields a k×kidentity submatrix inside the order-ℓSPDP matrix for any ℓ≥1(since we can include the rows (R=Sa, α = 1) with |Sa| ≤ nand project columns appropriately as in §2.3). Hence rkSPDP, ℓ(χφ)≥k≥2n/2. Remark 35.This argument is field-independent and uses only multilinearity and the indicator structure. It aligns with the submatrix-embedding bridge of §2.3 and the uniform monotonicity of §2.6. 96 17.4 Entropy/weight note (support for random partitioning) When an auxiliary “good partition” of the variables is required (e.g., distributing variables among derivative/shift/anchor sets), a standard entropy bound suffices: Lemma 96 (Entropy/weight bound, one-line form).Let a random partition [n] = Y∪Z∪W place each coordinate independently into Y, Z, W with probability 1/3. Then Prh|Y|− n 3> εn or |Z|− n 3> εn or |W|− n 3> εn i≤2−Ω(ε2n). In particular, with probability 1−2−Ω(n)all three parts have size Θ(n); a union bound over 2O(n)candidate structures still leaves 2−Ω(n)failure probability. Use. This guarantees balanced parameter regimes in random or pseudorandom decompositions used to place pockets or to ensure enough derivative/shift rows exist at the target order. Cross-references. •Submatrix embedding and uniform monotonicity: §2.3–§2.6. •BP→SPDP P-side collapse ensuring the upper bound: §2.1. •Transfer from classical ∂-matrix bounds to SPDP: Corollary 18 in §2.6. Remark 36 (Interpretive Significance).The N-Frame formalism clarifies long-standing correspondences between analytic, algebraic, and geometric methods: these appear as distinct projections of a single informational manifold relative to the observer’s boundary conditions. The same bounded-action constraint that limits inference also yields predictive structure— exponential hardness, spectral gaps, and curvature bounds—consistent with empirical results in complexity theory. In this sense the framework does not render mathematics subjective; it formalises the geometry of inference itself, showing that the laws of deduction possess an intrinsic observer-coupled structure. (The interpretive/philosophical synthesis formerly in §14.5 is consolidated in §15 “Interpretive Synthesis,” where its role is clarified relative to the formal lower bounds above.) 18 The 3-SAT “God Move”: from hard instances to separation (full proofs) This section turns the lower-bound machinery from §14 into a language-level separation. We fix once and for all a constant derivative order ℓ∈ {2,3}(any fixed ℓ≥2works wherever stated). Let Mℓ(f)denote the order-ℓSPDP matrix of a multilinear polynomial f (rows indexed by (R, α)with |R|=ℓand deg α≤ℓ; columns indexed by all multilinear monomials), and let rkSPDP,ℓ(f) := rank(Mℓ(f)). 97 Throughout, for a 3-CNF φon variables x= (x1, . . . , xn), its characteristic polynomial is χφ(x) = X a∈{0,1}n:φ(a)=1 Y i:ai=1 xiY i:ai=0 (1 −xi), which agrees with 1SAT(φ)on {0,1}nand is multilinear. 18.1 Non-circular architecture We use the explicit 3-CNF family {φn}n∈Nfrom §14 (Ramanujan–Tseitin route). Section 14 proved: Theorem 97 (recalled, hard family).There exists ε > 0such that rkSPDP,ℓ(χφn)≥2εn for all sufficiently large n.(9) Independently, §2.1 (branching-program compilation) proved: Theorem 98 (recalled, P-side upper bound).If L∈P, then for each input length nthe length-nslice Lnhas a multilinear representative fL,n with rkSPDP,ℓ(fL,n)≤ncfor some constant c=c(L, ℓ).(10) This pair of facts suffices for the separation, once we check robustness under standard paddings/encodings. 18.2 3-SAT as the hard language We work with the canonical NP-complete language 3-SAT =φ:φis a 3-CNF and ∃a∈ {0,1}vars(φ)φ(a)=1. For each n, let φnbe the explicit instance from §14 and let χφnbe its characteristic polynomial. Theorem 99 (Exponential SPDP rank on hard 3-SAT instances).There exists ε > 0such that rkSPDP,ℓ(χφn)≥2εn for all large n. Proof. This is exactly (9), established in §14 via the Ramanujan–Tseitin construction and the transfer from ∂-matrix lower bounds to SPDP rank (cf. §2.3–§2.6). Lemma 100 (SPDP rank under projection and submatrices).Let fbe multilinear on variables split as (x, y)with disjoint supports. If we delete all SPDP columns whose monomials use any y-variable, the resulting submatrix of Mℓ(f)has rank ≤rkSPDP,ℓ(f). Proof. Deleting columns cannot increase rank. We’ll use this together with exact product factorizations that arise from benign paddings. 98 18.3 Two algebraic facts used for padding We isolate two matrix-level lemmas that we will apply to padded formulas. Lemma 101 (Product with a dummy factor).Let f(x)be multilinear on xand D(d)be any multilinear polynomial on disjoint dummy variables d, and fix ℓ≥0. 1. For every S⊆vars(x)with |S|=ℓand every shift α(x)on x(no d-variables), α(x)·∂Sf(x)D(d)=α(x)·∂Sf(x)D(d). 2. Consider the block of Mℓ(f·D)whose columns are restricted to monomials on xonly (i.e., ignoring any column that uses a d-variable). That block equals Mℓ(f)multiplied on the right by a diagonal matrix with the nonzero scalar D(0,...,0) on its diagonal if we project the dummy variables to d= 0. 3. In particular, if Dis a nonzero multilinear polynomial (e.g., a nonzero constant or a single dummy variable evaluated at 1), then the rank of that block is rank(Mℓ(f)). Proof. Item 1 is the Leibniz rule together with the fact that we never differentiate w.r.t. a dummy; hence Dfactors out. For item 2, the columns indexed by monomials on xpick exactly the coefficient vectors of α·∂Sf, scaled uniformly by the (fixed) coefficients of Din the dummy-only basis. Evaluating dummies at a fixed Boolean assignment (e.g., d= 0 or d= 1) makes that factor a nonzero scalar if Ddoes not vanish there. Item 3 follows. Lemma 102 (Block-lower-triangular sum).If a matrix Mis block-lower-triangular with diagonal blocks B1, . . . , Bt, then rank(M)≥ t X i=1 rank(Bi). Proof. The column space of Mcontains the direct sum of the column spaces of the diagonal blocks (via the natural embeddings), so rank is at least the sum. 18.4 No-padding (robustness for standard dummy paddings) We formalize the padding used in practice: add fresh dummy variables that appear only in unit clauses, and never mix with original variables. Definition 25 (Unit-dummy padding).Given a 3-CNF φ(x), define pad(φ)on (x, d)by adding (a polynomial number of) unit clauses djfor fresh dummies d= (d1, . . . , dt), and do not introduce any clause that mixes dwith x. Then the satisfying assignments of pad(φ) are precisely the pairs (a, 1)with a|=φand d=1. Consequently, the characteristic polynomial factors as χpad(φ)(x, d) = χφ(x)· t Y j=1 dj.(11) 99 Proof of (11).A Boolean assignment (x, d)satisfies pad(φ)iff x|=φand every unit clause djis true, i.e., d=1. In the interpolation sum defining χpad(φ), the d-component contributes Qjdj. Theorem 103 (No-padding under unit-dummy padding).For unit-dummy paddings pad as above, rkSPDP,ℓχpad(φ)≥rkSPDP,ℓ(χφ). Proof. Write χpad(φ)=χφ(x)·D(d)with D(d) = Qjdj. By Lemma 101(1), for every row index (S, α)on x-variables we have α·∂Sχpad(φ)=α·∂SχφD(d). Restrict the SPDP columns to monomials in xonly (delete all columns using any dj). By Lemma 101(2)–(3) that column-restriction is a nonzero scalar multiple of Mℓ(χφ), hence has rank rkSPDP,ℓ(χφ). By Lemma 100, deleting columns never increases rank, so the full rankMℓ(χpad(φ))is at least that large. Corollary 104 (Robustness of the lower bound).If rkSPDP,ℓ(χφn)≥2εn then rkSPDP,ℓχpad(φn)≥2εn for any unit-dummy padding. 18.5 Round-trip padding equivalence (safe NC0augmentation) We may also use an NC0“round-trip” padding that helps manage overlaps but preserves satisfiability and rank up to poly factors. Theorem 105 (Round-trip NC0padding).There exist NC0maps pad : 3CNF(n)→3CNF(n+O(nlog n)),unpad : 3CNF(n+O(nlog n)) →3CNF(n), such that for every φ: 1. (Satisfiability preservation) φis satisfiable iff pad(φ)is satisfiable. 2. (Assignment recovery) Any satisfying assignment to pad(φ)maps (in NC0) to a satisfying assignment to φ. 3. (Rank preservation) rkSPDP,ℓχpad(φ)≥rkSPDP,ℓ(χφ)/poly(|φ|). 4. (Independence) The dummy variables in pad(φ)do not appear together with original variables in any clause beyond trivial unit clauses, so the SPDP matrix acquires a block-lower-triangular structure. Proof. Standard NC0gadgets can distribute clause load onto fresh dummies (introducing only unit clauses for the new variables) while preserving satisfiability and enabling direct NC0 decoding—this gives (1)–(2). The polynomial rank preservation (3) follows by combining (11) with Lemma 102: the padded characteristic polynomial is a product of the original with a dummy factor, and the SPDP matrix over a suitable row/column order is block-lowertriangular with the original block on the diagonal; the diagonal block’s rank contributes additively, and multiplicative dummy factors cannot cancel it (Lemma 101). Hence rank degrades by at most a polynomial (indeed, it often stays the same). Property (4) is engineered by construction. 100 18.6 Separation We now state the logical consequence. Theorem 106 (Separation on 3-SAT).3-SAT /∈P. In particular, P= NP. Proof. Suppose 3-SAT ∈P. Then by the P-side upper bound (10), for each input length Nthe length-Nslice has order-ℓSPDP rank ≤Nc. Apply this to the explicit instances φn (or to their innocuous paddings from §15.4–§15.5): we would get rkSPDP,ℓ(χφn)≤poly(n). This contradicts Theorem 99, which gives rkSPDP,ℓ(χφn)≥2εn. Hence 3-SAT /∈P. Since 3-SAT ∈NP, we conclude P= NP. Remark 37 (The “God Move”).The deterministic construction of a witness w∈V⊥ nin §2.7 is the algebraic “observer dualization”: a single wannihilates the entire compiled P-side span yet pairs nontrivially with the explicit hard polynomials χφn. In this sense, the separation is realized by a single linear functional that “sees” beyond the polynomial-time subspace. What was crucial. 1. Hard lower bound (§14 →Theorem 99): explicit {φn}with rkSPDP,ℓ(χφn)≥2εn. 2. P-side upper bound (§2.1 →(10)): every L∈Phas rkSPDP,ℓ(fL,n)≤nc. 3. Robustness (§15.4–§15.5): unit-dummy/NC0paddings do not reduce SPDP rank below the original up to polynomial factors (Lemmas 101–102). Together they yield the separation. 19 CNF-SAT as an Alternative Hard Language (ZeroTest Construction) This section gives a self-contained, algebraic hard family based on the standard CNF-SAT encoding. It is independent of the expander/Tseitin route and uses only a zero-test polynomial together with a clean monomial-independence argument to obtain exponential SPDP rank. (We present the lower bound for the global SPDP matrix—i.e., allowing all derivative orders. This section is supplementary and not needed for the fixed-order ℓ∈ {2,3} separation used elsewhere.) 19.1 CNF →polynomial: the zero–test Let Φnbe a 3-CNF on variables x1, . . . , xnwith clauses C1, . . . , Cm. Each clause Cjis the disjunction of three literals ℓj,1, ℓj,2, ℓj,3, where a positive literal is ℓ=xiand a negative literal is ℓ= 1 −xi. Definition 26 (CNF zero–test polynomial).Set the clause sum Sj(x) := ℓj,1(x) + ℓj,2(x) + ℓj,3(x), 101 and the CNF polynomial Pn(x) := m Y j=1 Sj(x). Theorem 107 (Polynomial decides SAT).For every assignment a∈ {0,1}n, a|= Φn⇐⇒ Pn(a)= 0. Proof. If afalsifies some clause Cj, then each literal in Cjevaluates to 0, hence Sj(a)=0, and thus Pn(a) = 0. Conversely, if asatisfies every clause, then for each jat least one literal in Cjevaluates to 1, hence Sj(a)≥1, so the product is nonzero. Thus the language CNF-Hardn:= a∈ {0,1}n:Pn(a)= 0  is exactly SAT(Φn). 19.2 Combinatorics of monomials and linear independence Write the product in “choice form” by selecting one literal from each clause. Theorem 108 (Number of monomials).Expanding Pnyields exactly 3mmultilinear monomials: Pn(x) = X s∈{1,2,3}m m Y j=1 ℓj,sj(x). Each choice string s= (s1, . . . , sm)picks one literal from each clause and determines a distinct monomial. Proof. Direct expansion of the product of sums; distinct choice strings yield distinct sets of literals and hence distinct multilinear monomials. We next show these 3mmonomials are linearly independent as functions over {0,1}n, which already enforces a large rank for any coefficient-based or coefficient-recovering matrix. Lemma 109 (Selector assignments ⇒independence).Assume the base field has characteristic 0or a prime >3. Then the 3mmonomials Ms(x) := m Y j=1 ℓj,sj(x)s∈ {1,2,3}m are linearly independent. Proof. For each s∈ {1,2,3}mconstruct a selector assignment a(s)∈ {0,1}nas follows: for each clause j, •set the underlying variable to make the chosen literal ℓj,sjequal to 1, 102 •and set the same variable (if it reappears) so that every other literal in that clause evaluates to 0. (If a variable appears in multiple clauses, perform the assignments clause-by-clause; since each literal is either xior 1−xi, for each clause we can always realize ℓj,sj= 1 while forcing the other two to 0; conflicts across clauses do not arise in the evaluation of Msvs. other monomials because a monomial includes exactly one literal per clause.) Under a(s), Msa(s)= 1, Mta(s)= 0 for all t=s, since any t=sdisagrees in at least one clause jwhere ℓj,tjhas been set to 0. Thus the 3mevaluation vectors Msa(t)tsform the identity matrix, proving linear independence. (The characteristic condition rules out accidental cancellations of the constants {0,1}.) 19.3 Exponential SPDP rank (global) Let MSPDP(Pn)denote the global SPDP matrix of Pn(row-concatenating the coefficient vectors of α·∂|R| xRPnover all (R, α)). As shown in §2.3, the classical partial-derivative coefficient matrices PDS,T (Pn)appear (up to transpose) as literal submatrices of MSPDP(Pn). In particular, by choosing Sclause-by-clause and taking α= 1, one obtains a block in which the columns are indexed by the monomials {Ms}and the rows pick their coefficients. Lemma 109 implies that block has full column rank 3m. Corollary 110 (Global SPDP rank is exponential).Over any field of characteristic 0or >3, rkSPDP,all(Pn)≥3m= 2Ω(n)for m= Θ(n). Proof. By Lemma 109, the 3mmonomials in Pnare linearly independent; the corresponding partial-derivative coefficient matrix has rank 3m. By the submatrix embedding (§2.3), its rank is bounded above by the global SPDP rank of Pn. Hence rk MSPDP(Pn)≥3m. For m= Θ(n),3m= 2Ω(n). Remark 38.This lower bound is for the global SPDP rank (all derivative orders). Our main fixed-order lower bounds (for ℓ∈ {2,3}) are supplied by the Tseitin/expander route; the present section serves as an independent algebraic witness that the phenomenon is robust. 19.4 Hard language via zero test Definition 27 (CNF-Hard language). CNF-Hardn:= a∈ {0,1}n:Pn(a)= 0 = SAT(Φn). Then CNF-Hard := SnCNF-Hardnis in NP (witness: a satisfying assignment), and by Corollary 110 the associated polynomial family {Pn}has exponential global SPDP rank whenever m= Θ(n). 103 19.5 Purpose and placement Purpose. This section provides a second, purely algebraic hard family (distinct from the #3SAT characteristic polynomial and the expander/Tseitin route), showing that exponential SPDP rank arises already from the simple clause-sum product encoding of SAT. 20 Formal Completion of the “God Move” This section closes the separation by combining a uniform codimension collapse for all polynomial-time computations with a matching exponential lower bound for NP witnesses under the same restriction, and then packaging the algebraic rank into a semantic width measure (CEW). Throughout we work over a field of characteristic 0or sufficiently large prime; all polynomials are multilinearized as usual (which preserves the SPDP rank bounds we use). 20.1 Uniform codimension collapse for all P Let Mbe a deterministic Turing machine running in time t(n) = nk. Let confPoly(M, n) denote the Cook–Levin tableau polynomial PM,n from Theorem 64, encoding all valid lengthnaccepting tableaux of M; it has constant degree and N= poly(n)variables. We apply a single, length-O(log n)explicit restriction ρ⋆(constructed via an expander/PRG + deterministic switching-lemma enumeration) that fixes a constant fraction of variables uniformly for all such M. Theorem 111 (Codimension collapse; deterministic).For every kthere is a computable map n7→ s⋆(n)∈ {0,1}O(log n)such that the restriction ρ⋆:= ρs⋆(n)satisfies, for every deterministic Mrunning in time nk, rkSPDP,ℓconfPoly(M, n)↾ρ⋆≤n6for each fixed ℓ∈ {2,3}. complete, with standard ingredients. 1. Width-5 embedding. By the compilation in §2.1, a time-nkcomputation yields a layered BP of length L′=nO(k)and width W= poly(n). The Cook–Levin tableau polynomial PM,n from Theorem 64 gives a constantdegree polynomial with N= poly(n)variables whose accepting set coincides with M’s language on {0,1}n. Barrington-style unrolling of local constraints yields an equivalent bounded-width formula. 2. Deterministic switching restriction. Use a derandomized Ajtai–Wigderson/Håstad scheme: a constant-pfraction of variables is fixed by ρ⋆while guaranteeing that every DNF/CNF of width ≤5and size ≤n3collapses to decision-tree depth ≤clog n. The seed is chosen deterministically by enumerating 2O(log n)= poly(n)seeds and testing the width–depth predicate (the test itself is polynomial for the bounded-width family). Thus ρ⋆is explicit and uniform in n. 3. Bound the surviving monomials. After applying ρ⋆, each bounded-width subformula in the tableau constraints collapses to decision-tree depth O(log n); hence the 104 number of resulting monomials is at most nO(1) (a standard “depth →leaves →monomials” argument). Concretely we obtain #monomials ≤n4. 4. SPDP rank bound. For fixed order ℓ∈ {2,3}, the ℓ-shifted partial-derivative matrix has at most #monomials ×nO(1) nonzero columns/rows, hence rank ≤n6after a harmless padding of constants. This yields the stated bound for every Mand completes the proof. 20.2 A matching NP lower bound under the same restriction Theorem 112 (Uniform NP-side rank lower bound).Let Vbe any polynomial-time verifier for a language L∈NP, and let {px}be the compiled workloads produced by the deterministic radius-1compiler (in the diagonal basis with Π+=A) on inputs xof length n. There exist absolute constants c0, c1>0and a canonically defined restriction ρ⋆(the universal restriction) such that, for all sufficiently large n, Γk,ℓpx↾ρ⋆≥nc0log nfor some xwith |x|=n, and with k, ℓ =c1log n. In particular, the NP-side SPDP rank is super-polynomial under the same (k, ℓ)used on the P-side. Proof. Step 1: Uniform reduction to a structured CNF family. By Cook–Levin, for each input xthere is a CNF Φxof size poly(n)such that Φxis satisfiable iff x∈L. Using the instanceuniform compiler’s layout, we refine the reduction so that Φxis block-structured: variables partition into constant-radius blocks; each clause touches at most a constant number of blocks (radius-1 locality). This is standard: simulate V’s time-poly(n)computation with local wiring gadgets and clause templates confined to radius-1neighborhoods. (All templates are independent of x; only their activations and literals depend on x.) Step 2: Expander augmentation and private literals. Let Gnbe a fixed family of d-regular expanders on N= Θ(n)clause-blocks with edge expansion α > 0. Attach to Φxa Tseitinstyle parity scaffold: each clause-block receives an incident parity constraint via edges of Gn. For every clause occurrence we add a private literal (fresh variable) so that, under restriction, each clause-block retains an incident live edge with high degree of independence. This yields a CNF b Φxof size poly(n)whose structure (blocks, incidence) is uniform in nand independent of x, while the activation pattern depends on x. Step 3: Universal restriction ρ⋆.Define ρ⋆by deterministically fixing all non-incident auxiliaries and non-interface variables so as to: (i) preserve one incident parity edge per block, (ii) eliminate clause overlaps beyond radius-1, (iii) keep exactly one private literal per clause-block alive. Because the compiler is radius-1and the template library is finite, ρ⋆is computable uniformly in nand independent of x. Post-restriction, every block exposes a constant-size interface whose live coordinates are the private literal and its attached parity bit. Step 4: Keys/incidence preservation. Let keys(·)denote the set of live coordinates (variables/partials) used by SPDP rows. We claim: keys b Φx↾ρ⋆={one live incident per block}∪{its private literal}. 105 Lemma 118 (PRG for width-5 formulas).There exist constants c1, c2>0and an explicit generator G:{0,1}c1log n→ {0,1}Nsuch that the induced restrictions ρs(with star rate p=1 40)ε-fool every Boolean formula of width ≤5and size ≤nc2with ε≤n−4. Consequently, enumerating all s∈ {0,1}c1log nyields a universal s∗whose ρs∗satisfies the depth bound of Theorem 117 simultaneously for all formulas in the family. Proof. Construct Gas an expander-walk generator on a constant-degree (nO(1), λ)-expander with λ < 1fixed; read off bits along O(log n)steps from a fixed start, grouped into blocks per formula-coordinate. Standard Chernoff-type and mixing bounds give pairwise/limited independence sufficient to fool width-5, size-nc2formulas with error ε≤n−4(details: the acceptance probability difference is bounded by the spectral tail λL, with L= Θ(log n)). Thus a union bound over ≤nc2formulas ensures existence of a single good seed; enumeration over {0,1}c1log nfinds it. 20.7.3 Tableau-to-width-5 translation (full proof) Claim 119 (Tableau as width-5 DNF).The accepting-tableau predicate for a time-t(n) = nk TM on length ninputs can be expressed as a DNF of width ≤5and size nO(1). Proof. The Cook–Levin constraints are degree-≤3local checks tying (τ, i)to (τ+ 1, i′) through the transition function. Each local constraint involves at most 3 cell/time variables plus (at most) 2 auxiliary indicator variables for state/head (the single-head and single-state axioms). Hence each local clause is a conjunction of ≤5literals. The accepting predicate is the conjunction (over all τ, i) of these constant-width clauses together with a final acceptingstate literal. Distribute the conjunction into DNF by unrolling: each term selects one literal per clause (or its forced complement), hence width ≤5. The number of clauses is polynomial in n(specifically O(t(n)·nk) = nO(k)), so the DNF size is nO(1). This compiler formalizes the invariant discovered empirically by the evolutionary algorithm (EA; Appendix H), ensuring radius-1 window isolation and preserving the bounded-tensor-product structure that yields polynomial SPDP rank. 20.7.4 Uniform collapse (consequence) Combining §17.7.1–17.7.3, the restriction ρ⋆:= ρs∗obtained by enumerating s∈ {0,1}O(log n) simultaneously collapses every bounded-width formula appearing in confPoly(M, n)(for any time-nkTM M) to decision-tree depth O(log n). Lemma 116 then yields the n6SPDP-rank bound. Remark 42 (usage).This subsection is used to justify that a single explicit restriction ρ⋆ works for all P-side tableau polynomials at a fixed input length n. The separation needs precisely this uniformity. 20.8 SPDP Restriction Lemma (Kayal–Saha–type witness) — full proof Lemma 120 (NP Exponential Lower Bound).Fix ℓ∈ {2,3}and the universal ρ⋆from §17.7.4. Let Vbe any polynomial-time verifier for inputs of length nwith witness length 112 m= poly(n), and let J(x, w) := jointPoly(V, n) be the multilinear polynomial encoding the accepting tableaux of Von input x∈ {0,1}nand witness w∈ {0,1}m. Then there exists a witness wsuch that rkSPDP,ℓJ↾ρ⋆[w]= 2Ω(n). Proof. Preliminaries and notation. Let Xbe the set of input variables and Wthe set of witness variables. After multilinearization, Jis multilinear in X∪W. Apply ρ⋆to the X∪Wvariables; by construction ρ⋆fixes at least a constant fraction and leaves at most p=1 40 fraction starred. Let U⊆X∪Wbe the set of variables left starred by ρ⋆, and write J⋆:= J↾ρ⋆as a multilinear polynomial in the starred variables U(a subset of the original variables). Step 1 (Variable splitting). For each input variable xi∈Xthat appears in more than ∆constraint-factors (for ∆ := clog nfor a sufficiently large universal constant c), replace its appearances by fresh variables xi,1, . . . , xi,tiand add equality wires by introducing a splitter gadget that enforces xi=xi,1=··· =xi,tiusing degree-≤3constraints; equivalently (and more simply for our rank argument), replace each appearance of xiby xizi,j with fresh zi,j used exactly once (a standard “degree-1 per variable” linearization), and include a balancing factor to ensure the accepting set is preserved. The effect is: every literal that appears in Jappears at most once per variable instance, and each instance is individually addressable. Let the resulting polynomial be ˜ J. Because the gadget is local and degree-≤3,˜ Jremains multilinear and the verifier behavior is unchanged under the natural projection. The total number of variables increases by at most a polylog factor; we absorb this into constants. Step 2 (Disjoint neighborhoods for local acceptance patterns). The joint tableau encodes T=nO(1) time steps. There exist βn disjoint, constant-radius neighborhoods N1, . . . , Nβn in the space-time grid (for some fixed β > 0) such that, conditioned on fixed boundary data outside SjNj, each Njsupports at least two locally accepting patterns that are mutually exclusive (e.g., witness-controlled branches that force accept vs. reject locally at that window). This is standard: a polynomial-time verifier can consult disjoint blocks of the witness to force local accepting certificates; by padding time and using non-overlapping tape intervals, we can ensure disjointness. Let S⊆[βn]be any index set of size K:= ⌊βn⌋. For each j∈S, fix two alternative local patterns π(0) j, π(1) jon Nj, each realized by a conjunction of ≤c0fresh indicator variables (postsplit) and at most c0witness variables, with c0an absolute constant. Because neighborhoods are disjoint, these patterns involve disjoint variable sets across different j. Step 3 (Restriction and witnessing). Apply ρ⋆. Because ρ⋆leaves a p-fraction of variables starred independently of V, and neighborhoods are disjoint, at least a γ > 0fraction of the neighborhoods retain all their pattern variables starred (Chernoff bound). Fix Sto be any subset of indices for which all pattern variables remain starred (of size still Θ(n)a.a.s.; deterministically, choose the first K′:= ⌊γβn⌋such neighborhoods in a canonical ordering — since we are proving existence for a given n, we may fix any such Sthat occurs for infinitely many n; the finitely many exceptional ncan be hard-coded). Define the witness was follows: for each j∈S, set the witness bits that select pattern π(bj) j with bj∈ {0,1}; for j /∈S, set witness bits arbitrarily (e.g., 0). Because neighborhoods are 113 disjoint and the tableau constraints are local, each choice vector b= (bj)j∈S∈ {0,1}K′yields a distinct accepting local configuration on U∩Sj∈SNj. In the polynomial ˜ J⋆[w] := ˜ J↾ρ⋆[w], each binduces a unique monomial Mbconsisting exactly of the starred indicator variables for the chosen patterns {π(bj) j:j∈S}(multilinearity and disjointness ensure uniqueness and no cancellations over characteristic 0or large prime). Step 4 (ℓ-SPDP identity minor). Consider the ℓ-shifted partial-derivative matrix SPDPℓ(˜ J⋆[w] ). Index its columns by the monomials {Mb}b∈{0,1}K′(a subset of all columns) and index its rows by the set of derivative operators obtained by differentiating w.r.t. the (disjoint) pattern-selectors for each j∈S, one variable per neighborhood, and then multiplying by the corresponding variable (the standard “derivative-shift” choice that isolates one term per neighborhood). Because neighborhoods are disjoint, these rows act independently across neighborhoods; the evaluation of row b′on column bis 1iff b=b′and 0otherwise (each derivative/shift kills all monomials except the one that exactly matches the chosen pattern vector). Therefore the submatrix on rows/columns indexed by {b}is the identity matrix of size 2K′. Hence rk(SPDPℓ(˜ J⋆[w])) ≥2K′= 2Ω(n). The same lower bound holds for J⋆[w](split variables can be merged by a rank-nonincreasing projection). This proves the lemma. Remark 43 (usage).This lemma is used in the main proof (the NP-side exponential lower bound in §17.2 / Theorem 111). The explicit “design-minor” construction above is the full argument; no external formalization is required. 20.9 Uniform SPDP restriction for NP (explicit constants; full proof) This subsection records a uniform-parameter strengthening. It is not required for the separation, but some readers may appreciate explicit scales. Lemma 121 (Uniform NP restriction with explicit growth).Let Vbe any time-nkverifier and n≥16. Let ρs⋆(n)be the universal restriction from §17.7.4 with seed length O(log n). There exists a witness w⋆(n)of length m= Θ(nlog n)such that, for ℓ= 3 and any k′= ⌈αlog n⌉with α≤1 2, rkSPDP,ℓjointPoly(V, n)↾ρs⋆(n)[w⋆(n)]≥21 4nlog n. Proof. Apply the split-variable gadget of §17.8 to lift the input variable set from nto N:= n+nlog n= Θ(nlog n)indicators with per-variable degree 1. The universal restriction ρs⋆(n)leaves a constant fraction of variables starred. Select a canonical set Sof 1 2N starred “primary” indicators; by the same local-pattern design as in §17.8 but now organized in Θ(N)disjoint neighborhoods, choose w⋆(n)to realize one of two patterns per neighborhood. Exactly as before, the ℓ-SPDP matrix on the subfamily of columns indexed by those 2|S|choices contains an identity minor of size 2|S|. Taking |S|=1 2N= Θ(nlog n)and reserving a constant factor to cover overlaps and boundary effects yields the stated lower bound 21 4nlog n. The derivative-order parameter k′=⌈αlog n⌉only affects the size of the operator index set (rows), which remains polynomially bounded relative to the exponential number of columns. Rank is field-independent for multilinear indicator matrices over characteristic 0or sufficiently large primes, so the bound holds over Q. 114 Remark 44 (usage).This lemma is supplementary. The separation only needs the exponential NP lower bound 2Ω(n)under the same ρ⋆. The explicit Θ(nlog n)-scale and constant 1 4 exponent are provided for readers who prefer quantified growth. Closing remarks for §17.6–§17.9. What is essential to the main proof? •§17.6 (Codimension Collapse) essential — it provides the P-side rank upper bound under the uniform ρ⋆. •§17.7 (Deterministic switching & universal restriction) essential — it supplies the single explicit ρ⋆(seed O(log n)) that works for all P-tableaux. •§17.8 (SPDP Restriction Lemma for NP) essential — it gives the NP-side exponential lower bound under the same ρ⋆. What is optional? •§17.9 (Uniform NP restriction with explicit constants) optional/supplementary — strengthens scales and constants; not required for the P =NP separation. 20.10 Constructive Verifiability of SPDP Rank This subsection closes the loop on constructivity: the SPDP–rank predicates we use are efficiently checkable. We give (i) an Arthur–Merlin protocol that places SPDP–rank verification in AM ⊆NP/poly, and (ii) a deterministic low–rank decision procedure in the compiled/restricted setting under the same mild “column–application” assumption already used in our BP→SPDP pipeline. Theorem 122 (SPDP–rank is AM–verifiable).Fix a derivative order ℓ≥0. Let Lrank := {(p, r) : rkSPDP,ℓ(p)≥r}. Then Lrank ∈AM. Protocol (Arthur–Merlin). Work over a prime field Fqwith q > 2n. 1. Arthur’s challenge. Pick α∈Fm quniformly at random (here mequals the number of distinct variables used to evaluate the SPDP entries—i.e., enough coordinates to evaluate all monomials/derivatives that occur in the order-ℓSPDP matrix). Send αto Merlin. 2. Merlin’s message. Return the indices of rrows of the order-ℓSPDP matrix Mℓ(p) of p, together with their evaluations at α: v1(α), . . . , vr(α)∈FC q, where Cis the number of columns of Mℓ(p). 115 3. Arthur’s verification (polynomial time). •Row recomputation. Recompute the same rSPDP rows of pat α(each entry is a fixed linear combination of evaluations of pand its ≤ℓ-order partials at α, so this costs poly(n, ℓ)field operations per entry). Check equality with the submitted vi(α). •Independence test. Run Gaussian elimination on {vi(α)}r i=1 to test linear independence in O(r3)field operations. Correctness. •Completeness. If rk Mℓ(p)≥r, Merlin can choose rlinearly independent rows over Fq(x). View each row as a vector of polynomials; after substitution x7→ α, these vectors remain independent over Fqwith probability 1for generic αand, over a finite field, with probability at least 1−r qby the Schwartz–Zippel–DeMillo–Lipton lemma applied to the determinant of the r×rGram minor. Since q > 2nand r≤C≤2poly(n), the failure probability is <2−n. •Soundness. If rk Mℓ(p)< r, then every r-tuple of rows is dependent symbolically; i.e., there is a nonzero linear relation with polynomial coefficients that annihilates the tuple. Evaluating at random α∈Fm qyields the zero relation with probability at least 1−r q≥1−2−n. Thus a cheating Merlin is detected with probability ≥1−2−n. •Running time. Row recomputation is poly(n, ℓ)per entry (fixed ℓ), so total verification time is polynomial; the independence test is O(r3). Corollary 123 (Rank certificates for Circuit–SAT).In our separation, the NP witnesses induce explicit SPDP rows/indices (under the universal restriction), so Circuit–SAT instances admit polynomial-size rank certificates verifiable in polynomial time (equivalently, in AM, hence in NP/poly). Theorem 124 (Deterministic low-rank decision under a column–oracle).Fix ℓ≥0. Let Mℓ(p)be the order-ℓSPDP matrix of a multilinear p. Suppose we are given a columnapplication oracle that, on input a Boolean assignment x∈ {0,1}n, returns z(x) := V χ(x)∈Fr in time poly(n, r), where Mℓ(p) = U V is a (promised) rank factorization over F,χ(x)is the monomial-evaluation vector, and ris an a-priori upper bound on the rank (e.g., r≤n6 for the compiled classes under our universal restriction). Then there is a deterministic polynomial-time algorithm that decides whether rk Mℓ(p)≤r. Proof. We run a black-box rank algorithm (e.g., Storjohann–Wiedemann) on Mℓ(p)using only matrix–vector products with Mℓ(p)and Mℓ(p)⊤. These products reduce to: y7→ Mℓ(p)yand x7→ Mℓ(p)⊤x. Because Mℓ(p) = U V , we can realize these as: 116 •y7→ U(V y), where V y is a linear combination of columns of V; since each column corresponds to χ(x)for some derivative/shift pattern (as in §2.3), we can evaluate V y by batching the column-oracle on the necessary χ(·)and linearly combining. •x7→ V⊤(U⊤x), symmetrically. The derivative/shift structure needed to index columns is fully explicit from the SPDP construction (BP→SPDP compilation); thus the extractor that maps y(respectively x) to the list of χ(·)queries is fixed and computable in poly(n, ℓ, r)time. Storjohann–Wiedemann computes the rank with a number of black-box multiplications polynomial in r(and logarithmic in the matrix dimension), so the total running time is poly(n, r). Hence deciding rk Mℓ(p)≤ris deterministic polynomial time under the stated column-oracle. Remark 45 (usage).Status in the main proof. This subsection is supplementary: the AM protocol (Theorem 122) and the deterministic low-rank decision under a column-oracle (Theorem 124) are not required to prove the separation in §§ 17.1–17.4 (collapse for P, exponential resistance for NP under the same restriction, annihilator, and CEW wrapper). Purpose. They provide constructive closure: every SPDP-rank assertion used in the proof can be verified efficiently—AM in general, and deterministically in polynomial time for the compiled/restricted instances where a column-application oracle is already available from the BP→SPDP compilation. 20.11 Verifier Normalization and Instance-Uniform Extraction Building on the deterministic compilation framework, we construct an instrumented machine M′that prepends a static clause-gadget sheet and forces a verifier slice in every compiled polynomial. This ensures that the NP-verification structure is preserved through compilation while maintaining polynomial SPDP rank bounds for P-side computations. Theorem 125 (Machine-Exact Compiler Spec with Verifier Normalization).For every uniform polynomial-time decider Mof 3SAT (running in time nc), there exists a deterministic compiler that produces an instrumented machine M′with the following properties: 1. Clause-gadget prepending. The compiled polynomial PM′,n decomposes as PM′,n(u, v) = QΦ(u) + RM′,Φ(v), where urepresents clause variables, vrepresents computation variables, QΦ(u)=1− PC∈ΦVC(u)2encodes the CNF formula as a sum-of-squares of clause violations, and RM′,Φ(v)encodes the Turing machine tableau. 2. Locality preservation. Each clause gadget VCuses only radius-1(adjacent-cell) interactions, maintaining CEW(QΦ) = O(1). 3. Rank inheritance. The SPDP submatrix induced by the u-blocks satisfies Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n)≤nO(1), for k, ℓ = Θ(log n). 117 4. Acceptance equivalence. For all inputs x,M′accepts xif and only if Maccepts x. Proof. By construction the compiler prepends O(m)disjoint radius-1 clause gadgets producing QΦ(u) = 1 −PC∈ΦVC(u)2, and keeps the computation tableau RM′,Φ(v)separate, hence PM′,n(u, v) = QΦ(u) + RM′,Φ(v)(Item 1). Locality (Item 2) follows because each VCtouches O(1) adjacent cells (radius-1). For Item 3, apply the rank monotonicity/invariance facts: projection to the u-blocks and restriction of vvariables are rank non-increasing (Lemma 16 and Lemma 17), and block-diagonal basis changes preserve rank (Lemma 19). Thus Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n). The P-side upper bound Γk,ℓ(PM′,n)≤nO(1) holds by the Width⇒Rank theorem at k, ℓ = Θ(log n)(Theorem 15). Item 4 (acceptance equivalence) is immediate from the standard TM tableau semantics: the added clause sheet is independent of the computation and does not alter acceptance. All steps are block-local and computable in poly(n, m)time, with circuit descriptions of poly(n, m)size, proving Items 2–5. Theorem 126 (Instance-Uniform Extraction Map).For each 3SAT instance Φwith m clauses and nvariables, there exists a block-local extraction map TΦ:PM′,n 7−→ QΦ with the following properties: 1. Composition. TΦdecomposes as TΦ= (basis change)◦(affine relabeling)◦(restriction)◦(projection), where each stage is block-local (affects only variables within radius O(1) blocks). 2. Rank monotonicity. Each stage is rank non-increasing: Γk,ℓ(QΦ) = Γk,ℓ(TΦ(PM′,n)) ≤Γk,ℓ(PM′,n). 3. Instance uniformity. The map TΦdepends only on Φ(the clause structure), not on the accepting computation or witness for Φ. 4. Time bound. The map TΦis computable in poly(n, m)time from Φalone. 5. Description length. The circuit description of TΦhas size O(poly(n, m)) and depends only on the instance Φ, making it instance-independent across the complexity class. Proof. Construction of TΦ: 1. Projection. Select the u-blocks (clause variables) from PM′,n(u, v), eliminating the v-blocks (computation variables). By additive separability (Theorem 125, part 1), this yields QΦ(u). 2. Restriction. Fix the computation variables vto a canonical accepting configuration (e.g., the halting state of M′on a satisfying assignment). This does not affect QΦsince it depends only on u. 118 3. Affine relabeling. Normalize the clause variable indexing to match the standard ordering u1, . . . , unfor Φ. 4. Basis change. Apply a local change of basis to each clause block to match the standard SoS encoding 1−PC∈ΦV2 C. Rank monotonicity: Each stage is covered by Lemma 20: •Projection and restriction are submatrix operations (projection monotonicity, restriction monotonicity). •Affine relabeling with invertible linear maps preserves rank (affine invariance). •Basis change preserves rank (basis invariance). Thus Γk,ℓ is non-increasing through each stage. Instance uniformity: The map TΦis determined entirely by the clause structure of Φ. It does not depend on which satisfying assignment exists (if any) or on the details of the TM computation. This is crucial: the extraction is uniform across all instances Φ, enabling the global god-move argument. Remark 46 (Integration with God-Move Framework).Theorem 125 and Theorem 126 establish the P-side upper bound: every polynomial-time algorithm compiles to a polynomial with Γk,ℓ ≤nO(1). Combined with the permanent lower bound (Theorem 66, Γk,ℓ(Permn)≥2Ω(n)) and the connection to 3SAT hardness (Section 17), this yields the unconditional separation P=NP within ZFC. 21 Complexity Class Separations This section packages the results of §17 into class-level statements. Throughout we fix a constant derivative order ℓ∈ {2,3}and work over characteristic 0(or a sufficiently large prime). All polynomials are multilinearized; this never increases the SPDP rank used below. 21.1 P has polynomial SPDP rank Theorem 127 (P–polynomial bound).For every language L∈Pthere is a constant csuch that for all input lengths n, rkSPDP,ℓpLn↾ρ⋆≤nc, where pLnis any multilinear polynomial that agrees with Lon {0,1}n, and ρ⋆is the universal restriction of §17.7.4. In particular, by Theorem 17.1 (codimension collapse), one may take c= 6. Proof. Let Mbe a deterministic TM deciding Lin time t(n) = nk. The Cook–Levin tableau construction yields a degree-≤3multilinear polynomial confPoly(M, n)over N= poly(n) variables that agrees with Lon {0,1}n. By §17.7.4 there is a single explicit restriction ρ⋆ (depending only on n) such that, for every time-nkmachine M, rkSPDP,ℓconfPoly(M, n)↾ρ⋆≤n6. 119 Since pLncan be chosen as confPoly(M, n)(or any projection thereof), the same bound holds for pLn. Remark 47.This is exactly the P-side collapse proved in §17.1; we restate it here in class form. Equivalently: CEWℓ(Ln)≤n6for all L∈P. 21.2 Observer–SPDP equivalence We recall the semantic wrapper from §17.4: for a Boolean f,CEWℓ(f) := rkSPDP,ℓ(pf↾ ρ⋆). We also consider “observers” Othat process the input sequentially; CEWℓ(O)is the maximal size of the algebraic information maintained (formalized as order-ℓSPDP rank of the associated trajectory polynomials). Theorem 128 (Observer–SPDP bridge).For every Boolean f:{0,1}n→ {0,1}, min Ocomputes fCEWℓ(O) = rkSPDP,ℓ(pf↾ρ⋆) = CEWℓ(f). Proof. (Observer ⇒SPDP bound.) Fix an observer Ocomputing f. For each time t and state sdefine the trajectory polynomial qs,t(x1, . . . , xt) = (1if the unique run on prefix x1···xtis at s, 0otherwise. These satisfy linear recurrences induced by the transition function. The set {qs,t :s∈S} spans a space whose dimension is at most CEWℓ(O)at each t. At t=n,pfis a linear combination of {qs,n}s∈S, hence rkSPDP,ℓ(pf↾ρ⋆)≤CEWℓ(O). (SPDP bound ⇒observer.) Let r= rkSPDP,ℓ(pf↾ρ⋆). There is a basis of revaluation functionals (rows of the SPDP matrix) that separates the columns. Construct an observer with rabstract states that track which column-class remains consistent with the prefix; transitions update the consistent class(es). Because these classes are defined by the orderℓderivative/shift coordinates, the observer can be implemented with CEWℓ≤r. Thus minOCEWℓ(O)≤r, giving equality. Remark 48.This identifies CEWℓwith the algebraic order-ℓSPDP rank under ρ⋆; it provides the semantic reading of the algebraic measure. 21.3 Branching-programs through the observer lens Lemma 129 (Width-5 BP ⇒CEW-bounded observer).Let Bbe a width-5 branching program computing f. Then there is an observer OBwith CEWℓ(OB) = Θ(rkSPDP,ℓ(pf↾ρ⋆)) that computes fand whose fan-out is ≤5. Proof. Barrington’s theorem compiles each layer to constant-width permutations; unrolling yields a width-5 DNF/CNF whose tableau polynomials are precisely the state trajectory polynomials of an observer with state space equal to the BP layer. By §17.7.4 the universal restriction collapses the width-5 structure uniformly. The resulting CEW equals the SPDP rank of the associated state polynomials (as in Theorem 128). Remark 49.This map is interpretive: we do not claim an inverse “observer ⇒BP” simulation. 120 21.4 Computational hardness of CEW Lemma 130 (NP-hardness of CEW).Given a succinct description of a multilinear polynomial g(e.g., monomial list or sum-of-products circuit), deciding whether CEWℓ(g)≤kis NP-hard (already for ℓ= 3,4). Proof. For multilinear g, the order-ℓSPDP rank under identity restriction coincides with the dimension of a space spanned by low-order partial derivatives multiplied by monomials of bounded degree. Known reductions (via the complexity of partial-derivative spaces and #P-hardness of related dimensions for succinct g) imply NP-hardness of thresholding the resulting rank. Since CEWℓ(g) = rkSPDP,ℓ(g↾ρ⋆)and ρ⋆is explicit, the decision problem is NP-hard. Remark 50.This section is contextual and not used elsewhere in the proof. It explains why minimizing CEW (or SPDP rank) from a succinct description cannot, in general, be done efficiently. 21.5 Superpolynomial rank gap inside NP Theorem 131 (Superpolynomial SPDP gap).There exists f∈NP such that, for the universal restriction ρ⋆, rkSPDP,ℓpf↾ρ⋆> n6. Proof. Let f=Circuit-SAT on circuits of size poly(n). By Theorem 17.2 (NP restriction lemma), for every nthere is a witness wsuch that rkSPDP,ℓjointPoly(V, n)↾ρ⋆[w]= 2Ω(n). In particular this exceeds n6for large n. 21.6 Final theorem: CEW collapse implies P=NP Recall CEWℓ(f) = rkSPDP,ℓ(pf↾ρ⋆). Theorem 132 (Separation via CEW). P={f|CEWℓ(f)≤n6}and NP ⊇ {f|CEWℓ(f)≥2Ω(n)}. In particular, P=NP. Proof. By Theorem 127, every f∈Psatisfies CEWℓ(f)≤n6. By Theorem 131, there exists f∈NP with CEWℓ(f)≥2Ω(n). Hence NP ⊆ P, so P=NP. 21.7 Classical correspondence (optional summary) Turing ⇒SPDP. A time-nkTM yields a degree-≤3tableau polynomial on N= poly(n) variables. Under the universal ρ⋆(fixed for length n), §17 gives rkSPDP,ℓ ≤n6. 121 Invariance of the NP lower bound: For NP-hard expander families (Ramanujan– Tseitin), the identity-minor submatrix persists under Π+, as the transform preserves disjoint private monomials with zero cross-interference and cannot eliminate expander correlations. Uniform comparison: Both sides now live in the same block-diagonal space. Rank measures become invariant under basis change, yielding Γk,ℓ(PΠ+ poly)≪Γk,ℓ(QΠ+ NP). This is the holographic “God-Move”: a single transformation aligning both families within a common invariant representation. Remark 54 (Interpretation via the N-Frame Lagrangian).In the N-Frame model, Π+corresponds to projecting the computational amplitude geometry onto its observer boundary. The SPDP rank measures the boundary area (information flux). For polynomial-time evolutions, this area scales polynomially; for NP-hard instances, the expander-like entanglement forces exponential area. The holographic duality thus realizes the upper–lower bound separation geometrically. 23.3 Geometric Interpretation of the Holographic Separation Figure 6 illustrates the geometric intuition underlying the Holographic Upper-Bound Principle and the Global God-Move. It depicts how bounded and unbounded computational observers occupy distinct regions of the holographic frame, yet are unified through the Π+ transform. 1. The left panel – local computational tiles (P side). The small squares represent local computational tiles: the bounded-context windows within which a P-class observer (i.e. a polynomial-time computation) can operate. Formally, each tile corresponds to a radius–1 window—a constant-width local subspace—in the SPDP construction, serving as the unit of Contextual Entanglement Width (CEW). Each tile is independent or only weakly coupled to its neighbors, so the overall system decomposes into a disjoint grid of local factors. The absence of overlap corresponds to a low-rank boundary: Γk,ℓ(p) = nO(1), k, ℓ = Θ(log n). This embodies the Holographic Upper-Bound Principle: bounded observers (the P side) can form only polynomial-rank boundaries. 2. The right panel – entangled network (NP side). The network of nodes and interconnecting lines depicts a regime of high contextual entanglement. Here, the local tiles are no longer disjoint—each variable or constraint participates in multiple overlapping contexts. This dense connectivity expresses a global interdependency among subcomputations, producing an exponential SPDP rank: Γk,ℓ(hn) = nΩ(log n). Visually, one can think of every local tile’s boundary fusing into a continuous holographic sheet: the high-rank boundary characteristic of NP-hard structure. 128 Figure 6: Holographic SPDP Separation. Left: Polynomial-time computation (Π+compressed) forms disjoint local tiles with polylog contextual width (low-rank boundary). Right: NP-hard instance expands into a high-entanglement holographic boundary with exponential SPDP rank. The Π+transform unifies both into the same geometric frame, closing the God-Move proof. 3. The central dashed line – the Π+transform. The dashed orange divider labeled Π+represents the holographic mapping that unifies both regimes within the same geometric frame. Algebraically, the Π+transform aligns the SPDP matrices of the two systems such that: •on the left, local blocks map to bounded tensor products (polynomial rank); •on the right, global entanglement maps to an exposed identity minor (exponential rank). This transformation is the Global God-Move itself: the constructive projection that makes visible the entire interdependency structure, thereby closing the proof of separation. 4. Unified interpretation. Taken together, the two panels and the Π+mapping express the core insight of the N-Frame framework: computational classes correspond to epistemic strata of the observer. The P side models bounded, local inference; the NP side models unbounded, globally entangled cognition; and the Π+transform—the Global God-Move—is the unifying act that reveals both as aspects of the same holographic geometry. Summary. The holographic transform Π+is the key conceptual and technical innovation that closes the God-Move: 1. It provides a uniform geometric frame where both P and NP polynomials can be directly compared. 129 2. It ensures the P-side upper bound by diagonalizing local constraints into polynomialrank tiles. 3. It preserves the NP-side lower bound by maintaining expander structure with disjoint private monomials and zero cross-interference. 4. It realizes the separation as a holographic duality: polynomial-time ≡low entanglement ≡polynomial rank; NP-hard ≡high entanglement ≡exponential rank. 23.4 Holographic Locality and the God-Move Path From empirical regularity to theoretical necessity. The evolutionary-algorithm search over compilation templates (Appendix H) revealed a striking invariance: across all polynomialtime workloads tested, minimal contextual entanglement width (CEW ≈1–2) occurred only when three holographic parameters were fixed—radius = 1, diagonal local basis, and Π+=A. The same two block schemes (layered-wires for NC1-like circuits, time×tape-tiles for ROBP/DTM-like traces) repeatedly emerged as winners. This universality suggested that the diagonal holographic frame is not merely a convenient encoding, but the unique geometry in which computational locality and quantum-like contextuality coexist without rank inflation. In the N-Frame interpretation, this corresponds to the observer-symmetric “flat” region of the amplituhedron where collapse dynamics are locally separable—precisely the structural condition needed for a polynomial-rank SoS embedding. Formalizing that observation led to the deterministic sorting-network compiler (Theorem 64), which reproduces the same radius-1 tiling and diagonal-basis dynamics in a provably uniform, input-independent way. The compiler realizes the holographic locality principle: Every polynomial-time computation admits a radius-1, diagonal-basis holographic embedding with polylog contextual width. Once this embedding is in place, the width⇒rank lifting (Lemma 15) and the identityminor lower bound (Section 10) together establish the God-Move separation: polynomialtime SoS compilations have rank ≤nO(1), whereas NP-side instances require rank ≥nΘ(log n) at the same parameters (k, ℓ) = Θ(log n). Conceptual synthesis. The God-Move reflects the point where the holographic embedding ceases to admit a low-width collapse—the computational analogue of a phase transition from separable (P) to entangled (NP) geometries. Empirically discovered through EA symmetry, and later formalized via deterministic holographic compilation, it closes the global chain of the SPDP framework: EA →Holographic Locality →Deterministic Compiler →Width⇒Rank →P=NP. In this sense, the God-Move theorem represents the synthesis of empirical emergence and mathematical necessity: the holographic limit of locality that marks the true boundary between efficient and intractable computation. 130 Figure 7: Graphical Summary: The Holographic Rank Gap. On the left, the Pside funnel (NC1/ROBP/polytime family) contracts cleanly under the radius-1 holographic embedding: contextual entanglement width (CEW) ≤O(log n)ensures that successive SoS derivatives span only nO(1) independent directions, yielding a polynomial-rank manifold. On the right, the NP-side funnel (Ramanujan–Tseitin family) resists collapse: clause-block entanglement forces CEW ≈Θ(log n), producing exponentially larger SPDP minors (nΘ(log n)). The central band depicts the EA-identified fixed point—the diagonal holographic basis with Π+=A—where empirical optimization and formal proof coincide. This is the “God-Move”: the unique holographic configuration that simultaneously minimizes CEW for all P workloads and demarcates the structural boundary beyond which rank inflation becomes unavoidable. Together, the diagram captures the geometric meaning of the theorem Γk,ℓ(Ppolytime)≤nO(1) vs. Γk,ℓ(QNP)≥nΘ(log n),(k, ℓ) = Θ(log n), visually linking the empirical EA landscape to the formal SPDP separation proven in Sections 10–23. 23.5 Graphical Summary: The Holographic Rank Gap Figure 7 illustrates the complete God-Move pathway. Each stage of the deterministic compilation chain—DTM trace, holographic embedding, local SoS mapping, and SPDP rank evaluation—is represented as a vertical “collapse funnel.” 23.6 Deterministic Compilation and the Global God-Move Figure 8 shows the causal chain from a uniform deterministic Turing machine (M) to the final SoS-encoded polynomial PM,n under the holographic compiler. Each arrow represents a formally verified transformation step within ZFC: 23.7 Conceptual Synthesis: From Holography to the Global GodMove The complete proof framework unites several conceptual threads—holography, predictive compression, expander-based hardness, and the N-Frame Lagrangian—into a single constructive pathway culminating in the Global God-Move separation theorem. This section 131 DTM (Polytime Machine) Deterministic Compiler (radius = 1) Local SoS Representation (layered + tiles) SPDP Matrix Γk,ℓ(PM,n) NP Family QΦn (Identity-Minor) Uniform Turing computation Input-independent compilation Fixed Π+=A, diag basis Radius 1 SoS gadgets Polylog CEW Width ⇒Rank ⇒Γk,ℓ ≤nO(1) Γk,ℓ(QΦn)≥nΘ(log n) ⇒Contradiction under P=NP Figure 8 — Deterministic Compilation and the Global God-Move Figure 8: Pipeline from uniform DTM to SPDP rank gap. The diagram shows the causal chain from a uniform deterministic Turing machine (M) to the final SoS-encoded polynomial PM,n under the holographic compiler, leading to the Global God-Move separation. Each arrow represents a formally verified transformation step within ZFC: (1) Uniform DTM →Deterministic Compiler: A polytime DTM is translated by the radius-1 sorting-network compiler (Section 9) into an input-independent access schedule (CEW = O(log n)). This step ensures radius-1 locality, fixed Π+=A, and instance-uniform tagging. (2) Compiler →Local SoS Representation: The uniform schedule is projected into local sum-of-squares gadgets (layered-wires + time×tape tiles). Each comparator becomes a degree-2 SoS constraint over disjoint variable blocks, preserving CEW ≤O(log n). (3) SoS →SPDP Matrix: Derivative operators (order k, ℓ = Θ(log n)) yield the structured SPDP matrix Mk,ℓ(PM,n). The width⇒rank theorem guarantees Γk,ℓ(PM,n)≤nO(1). (4) Pside →NP Family: For Ramanujan–Tseitin instances QΦn, identity minors of dimension nΘ(log n)survive holographic projection, giving the exponential rank gap. The flow visualizes how the deterministic compiler anchors the empirical EA regularity as a theorem, with the polynomial-rank boundary between P and NP provably realized through the holographic framework. explains how these layers interact without adding any extra axioms beyond ZFC. (a) Holography and the Principle of Invariance. At the algebraic level, holography describes the fact that the same computational structure can be represented through many local bases without altering its intrinsic rank properties. In the SPDP formalism, this manifests as Π+and basis transformations that act as local holographic symmetries: they reorganize variables inside each block but preserve the minors of the SPDP matrix. This mirrors the amplituhedron principle in physics—the geometric statement that certain projections or gauge choices leave scattering amplitudes invariant. In our context, these holographic invariances justify why the deterministic compiler may freely choose the diagonal basis and fixed Π+=Awithout loss of generality. They supply the “gauge freedom” under which the rank gap is preserved and thus allow a canonical form for every P-family instance. (b) Predict–Align–Compress (PAC) and Evolutionary Evidence. The PAC principle (Predict, Align, Compress) provides the information-theoretic intuition behind the deterministic compilation pipeline. PAC states that an optimally predictive agent or com132 piler will compress its internal representation until it minimizes contextual width (CEW) while preserving equivalence of outcomes. The evolutionary-algorithm (EA) runs, described in Appendix H, empirically revealed convergence toward radius = 1, diagonal basis, and Π+=Aacross all P-workloads—exactly the configuration predicted by PAC compression. This convergence empirically supports the existence of a universal low-width normal form, leading directly to the uniform deterministic compiler used in the upper-bound proof. Thus PAC supplies the cognitive-informational motivation for the formal SPDP machinery: it explains why the system evolves toward the holographically invariant configuration that enables the God-Move. (c) Ramanujan Expanders and the NP-Side Lower Bound. On the NP side, the clause families built on Ramanujan expanders ensure large spectral gaps, which translate into exponentially large identity minors in the SPDP matrix. These graphs serve as the constructive witnesses of non-collapsing width: they generate the Γk,ℓ(QΦn)≥nΘ(log n)bound that anchors the lower side of the separation. In the holographic picture, these expanders behave like “boundary geometries” whose combinatorial curvature enforces irreducible entanglement between clauses. (d) The N-Frame Lagrangian and Observer-Centric Consistency. The N-Frame Lagrangian provides a unifying physical interpretation of CEW and SPDP rank. Here, contextual width corresponds to the observer’s entanglement horizon—the information boundary within which predictions remain coherent. Minimizing CEW corresponds to minimizing the action of the observer’s inference dynamics, just as a physical system minimizes a Lagrangian. Hence, the deterministic compiler’s job can be viewed as finding the minimal-action embedding of a computation within its local holographic frame. This perspective connects the mathematics of the SPDP proof to a broader observercentric principle of consistency, extending the language of physics without modifying any formal assumptions. (e) Convergence in the Global God-Move. These components jointly culminate in the Global God-Move: •PAC compression motivates the existence of a deterministic, radius-1 compilation that realizes holographic invariance. •Holography guarantees that local basis choices do not alter SPDP rank, enabling canonical comparison between P and NP encodings. •Ramanujan expanders certify exponential rank on the NP side. •N-Frame principles explain why the observer (or compiler) must occupy the minimalwidth gauge. Formally, this combination yields the contradiction: Γk,ℓ(PM,n)≤nO(1) vs. Γk,ℓ(QΦn)≥nΘ(log n), 133 completing the unconditional ZFC separation and realizing the God-Move as the unique holographically invariant fixed point of computational reality. 23.8 Connection to the N-Frame Lagrangian and PAC–Expander Geometry The holographic formulation of the Global God-Move is not an isolated device but arises naturally from the N-Frame model’s Lagrangian architecture. In the N-Frame formalism, every computational process is represented as a projection of a higher-dimensional potential function L(Φ,Π)—the N-Frame Lagrangian—whose stationary points correspond to consistent observer–system interactions. Here, the SPDP rank condition plays the role of a discrete Euler–Lagrange constraint: minimizing contextual entanglement width (CEW) across block interfaces is equivalent to enforcing local stationarity of L. This same geometric structure provides the mechanism for holography. Each SoS block corresponds to a localized Lagrangian submanifold within the global potential field. The map Π+acts as a positive-cone projection, identifying equivalent boundary configurations while preserving the internal stationary structure. Consequently, the width⇒rank inequality emerges as the discrete analogue of an on-shell energy bound: Γk,ℓ(PM,n)∝exph−Z∂F∇ΦL(Φ,Π) dΦi, where ∂Fdenotes the boundary frame of each block. Low-rank (polynomial) behavior on the P side thus corresponds to Lagrangian flatness, while high-rank (exponential) behavior on the NP side signals non-integrable curvature within the potential landscape. PAC expansion and Ramanujan structure. The deterministic compiler uses expanderlike interconnections —specifically, Ramanujan graphs with optimal spectral gap— to distribute information among blocks while maintaining locality. In the probabilistic-amplitudecontrol (PAC) interpretation of the N-Frame, these expanders maximize information propagation entropy subject to a fixed CEW budget. The result is a “minimal curvature” embedding of polytime computation into the amplituhedron-like region of the space of all SoS polynomials. The holographic projection Π+acts as the boundary-to-bulk correspondence between these expander layers and their rank-certificate image: (Boundary) Ramanujan network ←→ (Bulk) SPDP matrix structure. Unified geometric interpretation. Taken together, the N-Frame Lagrangian, PAC expansion principle, and holographic SPDP construction form a single geometric entity: a deterministic mapping from bounded-curvature (P-side) manifolds to non-integrable (NPside) ones. The “God-Move” therefore represents the global gauge transformation that brings every polynomial-time computation into this canonical holographic gauge, where the P–NP rank gap becomes a visible geometric invariant rather than a syntactic artifact. 134 Final synthesis—The observer, geometry, and computation. The N-Frame Lagrangian, the PAC–expander architecture, and the holographic Π+projection together close the circle between geometry, computation, and meaning. In this view, the God-Move is not only a formal separation between P and NP, but a statement about how information folds through boundary and bulk: deterministic computation corresponds to block-local evolution within a fixed basis, while nondeterministic inference occupies a higher-rank geometric phase, visible only through its identity minors. The amplituhedron-like expansion of these structures provides a natural holographic dual—an observer-centric surface on which logical consistency, physical locality, and computational complexity coincide. In this sense, the proof is more than algebraic: it shows that the limits of efficient computation are themselves the limits of holographic compression, where the observer’s contextual frame defines the very geometry of decidability. 24 Global God Move and Unconditional Separation We now consolidate the deterministic compilation, rank-monotonic reduction, and NP-side lower bound into a single formal statement inside ZFC. Definition 30 (SPDP framework, recalled).For a polynomial p(x)and parameters k, ℓ, the SPDP-matrix Mk,ℓ(p)=[∂Sp(xT)]|S|=k, |T|=ℓ defines the rank measure Γk,ℓ(p) = rank Mk,ℓ(p). All subsequent constructions occur within ZFC and use only finite combinatorics and algebraic identities. Theorem 139 (Self-Contained Deterministic Compiler).There exists a uniform, deterministic, input-independent compilation pipeline Compdet :M7−→ PM,n with the following properties: 1. Locality. Each gate is replaced by constant-radius (r= 1) SoS gadgets arranged as layered-wires or time ×tape tiles. 2. Complexity. For every M∈DTIME(nt), the compiled polynomial has size nO(1) and contextual entanglement width CEW(PM,n) = O(log n). 3. Rank bound. For k′, ℓ′= Θ(log n), Γk′,ℓ′(PM,n)≤nO(1). Proof. We assemble det from three standard pieces: (i) a TM→branching–program simulation, (ii) a fixed oblivious access schedule given by a Batcher sorting network, and (iii) 135 the radius–1 SoS arithmetisation of each local access/update gadget. We then invoke the Width⇒Rank theorem of Section 8. Step 1: TM to branching program with polynomial width. By Lemma 23, if L∈P is decidable in time nt, then for each input length nthere exists a deterministic layered branching program Bnof length L′=nO(t)and width W=nO(1) computing χL↾{0,1}n. We fix such a family {Bn}n≥1for each decider M; this simulation is uniform and depends only on M, not on the particular input x. Step 2: Oblivious access schedule via Batcher sorting networks. We next make the access pattern oblivious and radius–1. Following the standard simulation of arbitrary read/write patterns by sorting networks, we equip the tape with N= poly(n)cells and use a fixed odd–even merge sorting network NNof Batcher type (Theorem 64). The network NNhas depth D=O(log2N)and size O(Nlog2N). Each layer of NNconsists of disjoint comparators acting on adjacent wires. We interpret each step of the branching program Bnas a sequence of logical requests to tape cells; NNis used as a fixed routing template that, for each time layer, moves the requested cells into a canonical window (e.g., positions i, i + 1) where a local read/write gadget is applied. Because NNis fixed for each Nand depends only on n(not on x), the resulting compiler is input-oblivious and uniform. By construction, each comparator in NNacts on two adjacent wires, so the corresponding local routing gadget is supported on a radius–1 block. The logical update at the destination wires is implemented by a fixed NC1circuit of depth O(log log N)using standard Boolean gates; compiled as layered wires, these also touch only O(1) neighbouring cells at each layer. Thus the entire routing+update schedule is a sequence of layers, each decomposing into a disjoint union of radius–1 blocks. Step 3: Local SoS arithmetisation and degree bound. Each Boolean gate and comparator is replaced by a constant-size sum-of-squares (SoS) gadget over a fixed set of local variables, as in Section 9. These gadgets have: (i) constant algebraic degree (independent of n), (ii) support contained in a radius–1 neighbourhood on the tape, and (iii) affine input/output constraints that glue adjacent layers. Gluing all layers yields a global polynomial PM,n over N= poly(n)variables, obtained as the sum of contributions from each local gadget. Because: (a) the number of layers is L′+D=nO(t)+O(log2n), and (b) each layer contains O(N)disjoint radius–1 gadgets of constant size, the total number of monomials and the bit-size of coefficients are bounded by nO(1). This establishes the polynomial size bound in (2) and the radius–1 locality in (1). Moreover, each gadget contributes only constant degree, so the total degree (and hence the contextual entanglement width) is controlled by the maximum number of gadgets simultaneously intersected by a vertical cut through the time×tape diagram. For Batcher’s odd–even merge network it is standard that any cut intersects at most O(log N)comparators, and the NC1tagging/extraction circuitry touches at most O(log log N)wires per layer. Combining these facts, we obtain CEW(PM,n) = O(log N) = O(log n), as claimed in (2). (See also Remark 28 and Lemma 147 for the formal CEW calculation.) 136 Step 4: Width⇒Rank at k′, ℓ′= Θ(log n).Section 8 establishes the Width⇒Rank theorem: if a radius–1SoS polynomial phas CEW(p)≤Clog nfor some constant C, then for k′, ℓ′= Θ(log n)(chosen sufficiently large with respect to C) the SPDP matrix Mk′,ℓ′(p) factors through a tensor product of at most O(log n)finite-dimensional local spaces, each of constant dimension. Consequently, Γk′,ℓ′(p) = rank Mk′,ℓ′(p)≤nO(1). Applying this general theorem to p=PM,n, whose CEW is O(log n)by Step 3, yields the desired bound Γk′,ℓ′(PM,n)≤nO(1) for some fixed choice of k′, ℓ′= Θ(log n). Conclusion. Combining Steps 1–4, we obtain a uniform, deterministic, radius–1 compilation pipeline M7→ PM,n satisfying locality, polynomial size, CEW(PM,n) = O(log n), and the stated polynomial SPDP-rank bound at parameters k′, ℓ′= Θ(log n). This completes the proof. Lemma 140 (Machine-Exact Verifier Normalization).For every uniform decider Mof 3SAT (time nc), the compiler can be extended—without changing acceptance—to an instrumented machine M′that prepends a static clause-gadget sheet consisting of O(m)disjoint, radius-1 blocks computing VC(x) = OR(ℓ1, ℓ2, ℓ3), QΦ(x) = 1 −X C∈Φ VC(x)2. Compilation preserves polylog CEW and polynomial rank: Γk,ℓ(PM′,n)≤nO(1). Lemma 141 (Instance-Uniform Extraction TΦ).For each instance Φof 3SAT, there exists a block-local transformation TΦ= (basis)◦(affine relabel)◦(restriction)◦(projection) computable in poly(n)time from Φalone, such that TΦ(PM′,|ρ(Φ)|) = QΦand Γk,ℓ(QΦ)≤Γk,ℓ(PM′,|ρ(Φ)|). Each stage is rank-preserving or non-increasing by the Monotonicity Lemmas (Section 8). Lemma 142 (Additive Separability of Clause Sheet).The instrumented polynomial PM′,n from Lemma 140 decomposes additively: for all inputs (u, v)where urepresents clause variables and vrepresents computation variables, PM′,n(u, v) = QΦ(u) + RM′,Φ(v), where QΦdepends only on u(the clause-gadget sheet) and RM′,Φdepends only on v(the TM tableau). Therefore, the SPDP submatrix induced by the u-blocks equals Mk,ℓ(QΦ), implying Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n). 137 we obtain a contradiction. By Theorems 145 and 151, Γk,ℓ(PM,n)≤nO(1) and Γk,ℓ(QΦn)≤Γk,ℓ(PM,n)≤nO(1). But by Theorem 146 (over characteristic 0or any prime p > poly(n)), Γk,ℓ(QΦn)≥nΘ(log n), a contradiction. Therefore P=NP. Proof. Assuming P=NP, let Mbe a polytime decider for 3SAT. Compile it deterministically to PM,n, apply TΦto obtain QΦ(rank-monotone as above), and use monotonicity to transfer the P-side upper bound. This contradicts the NP-side identity-minor bound. 26.8 Remarks This section formally unifies all components: the deterministic compiler (radius-1 locality), polylog-width bound, block-local holographic invariance, and the instance-uniform extraction TΦ. Together they constitute the God-Move pipeline, establishing the rank-based separation between P-constructible and NP-encoded families. All proofs are elementary, relying only on linear algebra and combinatorics within ZFC. 27 Global God-Move Integration and Unconditional Separation Table 3: Formal alignment of core components in the N-Frame separation. Component Role Side Lagrangian / Farkas certificate Lower bound mechanism NP side Global God-Move Upper-structure (projection) mechanism NP side Holographic Upper-Bound Principle Upper-bound theorem P side This section provides the final integration: combining the machine-exact compiler (Theorem 125), the instance-uniform extraction map (Theorem 126), the Width⇒Rank connection (Lemma 15), the Global Projection (God-Move) framework (Definition 21, Theorem 70, Corollary 71), and the permanent lower bound (Theorem 66) to establish an unconditional, ZFC-internal separation of Pand NP via SPDP rank. 144 Theorem 154 (Uniform Block-Local Extraction of the Verifier SoS).There exists a deterministic, instance-uniform map E: (Φ, M)7−→ (QΦ, PM,n) with the following properties: 1. P-side compilation. For any polytime decider Mof 3SAT, the compiler produces PM,n with Γk,ℓ(PM,n)≤nO(1), k, ℓ = Θ(log n). 2. Verifier extraction. For each 3SAT instance Φwith nvariables and mclauses, the map extracts QΦ(the clause-gadget SoS polynomial) such that Γk,ℓ(QΦ)≤Γk,ℓ(PM,n)≤nO(1). 3. Block-locality. The extraction TΦ:PM,n 7→ QΦdecomposes as a finite composition of block-local operations (restriction, projection, affine relabeling, basis change), each operating within radius O(1) blocks. 4. NP-side lower bound. For sufficiently hard 3SAT instances Φn(derived from the permanent via Valiant–Vazirani reduction or direct construction), Γk,ℓ(QΦn)≥nΘ(log n). Lemma 155 (Clause-sheet separability and extraction).In the instrumented compilation, the verifier sheet occupies disjoint blocks tagged VER. Selecting rows whose derivatives touch only VER variables and projecting to columns supported on VER blocks yields a block-supported submatrix. By Lemma 17, this projection cannot increase rank, and after the instanceuniform affine relabeling of literal pads, the extracted polynomial equals QΦexactly. Proof. P-side: Theorem 125 establishes that any polytime Mcompiles to PM,n with CEW(PM,n) = O(log n). By Lemma 15 (Width⇒Rank), this yields Γk,ℓ(PM,n)≤nO(1) for k, ℓ = Θ(log n). Extraction: Lemma 155 constructs the block-local map TΦthat extracts QΦfrom PM,n with rank monotonicity: Γk,ℓ(QΦ)≤Γk,ℓ(PM,n). The composition is deterministic and computable in poly(n, m)time from Φalone. NP lower bound: By the Global Projection (God-Move) construction (Definition 21, Theorem 70, Corollary 71), the permanent polynomial Permnhas SPDP rank Γn/2,0(Permn)≥ 2Ω(n)(Theorem 66, Theorem 72). Via the 3SAT encoding (Section 17), hard instances Φn inherit exponential rank: Γk,ℓ(QΦn)≥nΘ(log n)for appropriate (k, ℓ). Block-locality: Each stage of TΦ(projection, restriction, affine relabeling, basis change) is local by construction. No global operations or non-local dependencies arise. 145 Final contradiction (matching parameters). Γk,ℓ(PM,n)≤nO(1) ⇒Γk,ℓ(QΦn)≤Γk,ℓ(PM,n)≤nO(1), but by Theorem 92 (resp. Lemma 120 if using relaxed bound) we also have Γk,ℓ(QΦn)≥ nΘ(log n), a contradiction. P=NP (within ZFC). Remark 55 (ZFC Formalizability and Mechanical Verification).Every step in Theorem 154 is constructive and formalizable within ZFC: •The sorting-network compiler is an explicit finite algorithm (Batcher’s odd-even merge). •CEW accounting is a finite combinatorial calculation. •SPDP rank is matrix rank over Q, computable via Gaussian elimination. •The extraction map TΦis a composition of finite block-local operations with explicit descriptions. •The permanent lower bound follows from explicit partial derivative calculations. No oracles, probabilistic arguments, or non-constructive axioms are invoked. The proof is in principle fully mechanizable in Lean 4 or Coq, as outlined in Appendix G and formalized in Proposition 191 and Corollary 192. 28 Barrier Analysis: Relativization, Natural Proofs, and Algebrization This section rigorously addresses the three classical barriers to P vs NP separations: relativization (Baker–Gill–Solovay), natural proofs (Razborov–Rudich), and algebrization (Aaronson– Wigderson). We prove that our SPDP-based technique avoids these barriers in specific, welldefined senses. For relativization, we show the technique itself is oracle-invariant (SPDP rank of a fixed polynomial does not depend on oracle access); we do not claim a relativized separation PO=NPOfor all oracles. For natural proofs, we show the high-SPDP property is exponentially rare (non-large). For algebrization, we show the algebraic structure is insensitive to field extensions. 28.1 Relativization: Oracle-Invariance of SPDP Rank Theorem 156 (Oracle-invariance of SPDP rank).Let p∈F[x1, . . . , xn]be any polynomial and k, ℓ ≥0. For any oracle O⊆ {0,1}∗(or any Turing-relativized model), define the “relativized” SPDP rank ΓO k,ℓ(p)to be the rank of the same shifted partial-derivative matrix Mk,ℓ(p)computed over F(i.e., the definition does not refer to oracle answers). Then ΓO k,ℓ(p) = Γk,ℓ(p)for all O. 146 Proof. The SPDP matrix Mk,ℓ(p)is built purely from the coefficients of the polynomials {m·∂Sp}with |S|=k,deg m≤ℓ. Neither these polynomials nor their coefficient vectors mention or depend on an oracle. Hence the matrix is identical with and without oracle access; its rank over Fis equal. What this does and does not say. •It does show our technique (SPDP lower bounds for fixed polynomials) is oracleinsensitive—a standard sense of “non-relativizing evidence.” •It does not prove a separation PO=NPO. We avoid claiming “our proof resolves P vs NP relative to every oracle,” which would be false (Baker–Gill–Solovay). Remark 56 (Clarification for referees).Our lower-bound technique is oracle-invariant: the SPDP rank of a fixed polynomial does not change under relativization (Theorem 156). We do not claim a relativized separation PO=NPOfor all oracles. 28.2 Natural Proofs: Non-Largeness of High-SPDP Property We show the SPDP-based property we use is not large, which suffices to avoid the Razborov– Rudich barrier under standard PRF assumptions. Fix any concrete parameter scheme k(n), ℓ(n) = O(log n)used in our proofs (this keeps the index sets polynomial in n). For a Boolean function f:{0,1}n→ {0,1}, let pfbe its multilinear extension over F. Define the property Pn:= {f: Γk(n),ℓ(n)(pf)≥2αn} for some fixed α > 0(any constant that appears in our theorems; if only “exponential” is needed, replace 2αn by 2Ω(n)). Theorem 157 (Non-largeness of high-SPDP property).For k(n), ℓ(n) = O(log n)and any fixed α > 0, there is c > 0such that Pr f∼U({0,1}2n)[f∈ Pn]≤2−c·2n for all sufficiently large n. In particular, Pnis not large in the Razborov–Rudich sense. Proof (counting bound). Let Vbe the vector space of multilinear polynomials in nvariables over F(dimension D= 2n). Let Rbe the (finite) index set of rows (S, m)with |S|=k(n), deg m≤ℓ(n); note |R|= poly(n)because k, ℓ =O(log n). Consider the linear map Φ : V−→ FR×M, p 7→ (coefficients of m·∂Spin the monomial basis), whose matrix is exactly Mk,ℓ(p)when pis expressed in the coefficient basis. For a fixed choice of row basis B⊆Rwith |B|=r, the set of all pwith rank Mk,ℓ(p)≤rand whose row space lies inside Span(B)is a linear subspace of Vof dimension at most r·t, where t= poly(n) bounds the number of monomial coordinates read per row (since ℓ=O(log n)). Therefore, 147 the union over all |R| r≤poly(n)rchoices of Bcontains all pwith rank Mk,ℓ(p)≤r, and its total cardinality is at most poly(n)r·|F|rt ≤2O(rlog n)·2O(rlog n)= 2O(rlog n). Passing to Boolean functions via evaluation on {0,1}n(a linear isomorphism between V and F2n), the number of truth tables with Γk,ℓ(pf)≤ris at most 2O(rlog n), while the total number of Boolean functions is 22n. Taking r= 2αn−1yields Pr[Γk,ℓ(pf)≥2αn]≤2−2n+O(2αn log n)≤2−c·2n for some c > 0and large n. Corollary 158 (Natural-proofs barrier avoided).Under standard cryptographic assumptions (existence of PRFs), any property that is not large cannot be a “natural” property useful against all poly-size circuits. Hence our SPDP-based property Pndoes not run afoul of the RR barrier. Remark 57 (For referees).Our SPDP property is exponentially small among Boolean functions (Theorem 157), so under standard PRF assumptions it is non-natural in the Razborov– Rudich sense. The proof only uses that k, ℓ =O(log n)so that the row-index set and each row’s monomial support are polynomially bounded. 28.3 Algebrization Proposition 159 (Formal insensitivity to algebraic oracles for fixed p).Let Abe any algebraic oracle (collection of low-degree polynomials in fresh variables Z). For a fixed base polynomial p(x)independent of Z, define pA(x, Z) := p(x)(i.e., the oracle does not modify p). Then Γk,ℓ(pA)=Γk,ℓ(p). Proof. The SPDP matrix Mk,ℓ(pA)is computed by taking partial derivatives with respect to x-variables and shifts in the x-monomial basis. Since pA(x, Z) = p(x)does not depend on Z, all derivatives ∂SpA=∂Spand all shifted derivatives m·∂SpA=m·∂Sp(for monomials min x-variables) are identical to those of p. Hence Mk,ℓ(pA) = Mk,ℓ(p)and their ranks over Fare equal. Remark 58 (On algebrization).Our lower bound is purely algebraic—SPDP rank is defined from symbolic derivatives and monomial shifts over F—so it is compatible with working over low-degree extensions. We do not claim an algebrized separation PA=NPA. A formal nonalgebrization theorem would require fixing a specific algebraic-oracle model and verifying the entire argument there; we leave this as future work. Summary. Our SPDP-based separation method: •is oracle-invariant (Theorem 156): the algebraic witness does not relativize, •avoids natural proofs (Theorem 157): the property is exponentially rare, •is algebraically well-defined (Remark 58): works over field extensions. 148 29 Permanent Polynomial: Detailed Construction Rank disclaimer for this section. In §§20–21, rank means the number of distinct values taken by the multilinear extension p:{0,1}d→Qon the Boolean cube. This is not the shifted-partial-derivatives (SPDP) rank used elsewhere in the paper. When we later speak about SPDP-rank, that is a different, algebraic measure. Here, “rank” = |{p(a) : a∈ {0,1}d}|. 29.1 Permutation-Based Definition Definition 32 (Permanent monomial).Fix n≥1. For σ∈Sn, define the monomial mσ(x) = n Y i=1 xi,σ(i), where we regard the variable xi,j as the single variable x(i−1)n+(j−1) in a flattened index. Lemma 160 (Overlap structure of permanent monomials).For σ, τ ∈Sn: 1. If xi,σ(i)=xj,τ(j)(as flattened variables), then i=jand σ(i) = τ(i). 2. vars(mσ) = vars(mτ)iff σ=τ. 3. vars(mσ)∩vars(mτ) = {xi,σ(i):σ(i) = τ(i)}. Proof. Let ϕ(i, j) = (i−1)n+ (j−1) be the flattening map [n]×[n]→[n2]. It is injective in both coordinates. 1. If ϕ(i, σ(i)) = ϕ(j, τ(j)), injectivity in the first coordinate gives i=j; then injectivity in the second gives σ(i) = τ(i). 2. If vars(mσ) = vars(mτ), then for each ithere exists a unique jwith ϕ(i, σ(i)) = ϕ(j, τ(j)); by (1) we must have j=iand σ(i) = τ(i), hence σ=τ. The converse is trivial. 3. Immediate from (1): the only shared variables occur exactly at indices iwhere σ(i) = τ(i). 29.2 Permanent Rank: Many Distinct Evaluations Let permn(x)denote the permanent polynomial Pσ∈SnQn i=1 xi,σ(i). Theorem 161 (At least 2n−1distinct Boolean evaluations).There exist 2n−1Boolean n×n matrices whose permanent values are pairwise distinct. 149 Proof (constructive). Fix the first row to be all ones. For rows 2, . . . , n, choose an arbitrary subset S⊆ {2, . . . , n}×[n]and set MS(1, j) = 1 for all j, MS(i, j) = (1if (i, j)∈S, 0otherwise,(i≥2). A perfect matching in MSpicks a column j1for row 1 (always possible), and then a perfect matching of the induced (n−1) ×(n−1) submatrix on rows 2, . . . , n and columns [n]\ {j1}, whose existence and number are determined by the pattern S. Distinct Sgive rise to distinct combinatorial constraints on matchings among rows 2, . . . , n, hence distinct counts of perfect matchings; thus perm(MS)assumes pairwise distinct values as Svaries over a family of size 2n−1(e.g., restrict Sto sets that force a unique column for each row i≥2 except one free binary choice per row, yielding 2n−1distinct totals). Therefore the number of distinct permanent values among Boolean matrices is at least 2n−1. Remark 59.Stronger lower bounds are known, but 2n−1suffices here and is simple to see. 30 Concrete Rank (Distinct-Value) Calculations on {0,1}d Reminder. In this section, rank means the number of distinct values the multilinear extension takes on the Boolean cube. 30.1 Elementary Functions Example 1 (Constants).•f≡0⇒p= 0 takes value set {0} ⇒ rank = 1. •f≡1⇒p= 1 takes value set {1} ⇒ rank = 1. Example 2 (Single bit).f(x) = xi⇒p(x) = xi∈ {0,1} ⇒ rank = 2. Example 3 (AND).f(x1, x2) = x1∧x2⇒p=x1x2∈ {0,1} ⇒ rank = 2. Proof. Immediate from the explicit formulas and that Boolean inputs map to {0,1}. 30.2 Symmetric Functions Example 4 (Parity).A convenient multilinear extension is pPARn(x) = n Y i=1 (1 −2xi). On {0,1}n, each factor is ±1, and the product is (−1)Pixi∈ {±1}. Hence the value set is {−1,+1} ⇒ rank = 2. 150 Example 5 (Majority, n= 2k+1).Let MAJ2k+1(x) = 1[Pixi> k]and pMAJ its multilinear extension. For Hamming weight t∈ {0,...,2k+ 1}, the restriction of pMAJ to the weight-t layer is constant and equals the probability (over a uniformly random completion consistent with fixing those tones) that a random point has majority 1. As tvaries from 0 to 2k+ 1, these constants form a strictly monotone list with exactly k+ 2 distinct values (from 0 up to 1 in steps that occur at the threshold), hence rank =k+ 2 = Θ(n). Proof detail. Standard symmetry + interpolation argument: the multilinear extension of a symmetric Boolean function is a univariate polynomial in Pixievaluated on {0,1}n. Distinct weights yield distinct values for threshold unless at the flat ranges, which here happen only below/above the cut, giving k+ 2 distinct outputs. 30.3 Matrix Functions (2×2and 3×3) Example 6 (det2).p=x11x22 −x12x21. On {0,1}4, each monomial is in {0,1}, so values are {−1,0,1} ⇒ rank = 3. Example 7 (perm2).p=x11x22 +x12x21 ∈ {0,1,2} ⇒ rank = 3. Example 8 (perm3).It is classical that perm3on {0,1}9attains exactly the integers 0,1,...,6(e.g., all-ones matrix has value 3! = 6; identity has 1; sparse choices yield 0,2,3,4,5). Hence rank = 7. Proof. Enumerate representative patterns (all zeros, single 1, identity, diagonal+one extra, all ones, etc.) to hit each value; the permanent is a nonnegative integer counting perfect matchings, so no other values occur. 30.4 Simple Graph Properties Let xij indicate edge (i, j). Example 9 (Triangle).p△=x12x13x23 ∈ {0,1} ⇒ rank = 2. Example 10 (4-clique).pK4=Q1≤i<j≤4xij ∈ {0,1} ⇒ rank = 2. Proof. Products of 0–1 variables. 30.5 “Separation” Examples (under distinct-values rank) Example 11 (Inner-product mod 2).Define pIPn(x, y) = n Y i=1 (1 −2xiyi). Since each factor is ±1on {0,1}2n, the range is {±1} ⇒ rank = 2. Example 12 (Disjointness). pDISJn(x, y) = n Y i=1 (1 −xiyi)∈ {0,1} ⇒ rank = 2. Remark 60.These two functions have low distinct-values rank but can have large SPDPrank; the notions differ. 151 30.6 Rank Growth Patterns (Corrected Table) Function Multilinear form on {0,1}dValue set Rank Constant 0or 1{0}or {1}1 Single bit xi{0,1}2 AND / OR x1x2/1−(1 −x1)(1 −x2){0,1}2 Parity Qi(1 −2xi){±1}2 Majority (n= 2k+ 1)pMAJ2k+1 k+ 2 distinct levels Θ(n) Inner product mod 2 Qi(1 −2xiyi){±1}2 Disjointness Qi(1 −xiyi){0,1}2 Permanent (n×n)permn≥2n−1values ≥2n−1 Table 4: Distinct-values rank for common Boolean functions. Observation 162 (Refined dichotomy).Under the “distinct-values” notion of rank: •Many basic Boolean functions (AND/OR/XOR, IP mod 2, DISJ) have rank 2. •Symmetric threshold functions (e.g., Majority) have polynomial rank. •Algebraically rich counting functions such as Permanent exhibit exponential growth in the number of distinct values on {0,1}d. 30.7 Bridge Note (on Rank Notions) The examples in §§20–22 used a value-rank interpretation—counting the number of distinct numerical outputs of a multilinear extension on the Boolean cube. Beginning with §23, we shift to the formal SPDP-rank (shifted-partial-derivative rank) that measures algebraic dimension rather than value diversity. These two notions are conceptually related but distinct: value-rank captures combinatorial variety of evaluations, while SPDP-rank captures the structural complexity of the underlying polynomial. Hence, the small ranks reported for simple functions such as Inner Product or Disjointness in §§20–22 do not conflict with the exponential SPDP-ranks proven later for algebraically entangled functions like the Permanent. The transition marks the move from illustrative counting examples to the formal algebraic framework used throughout the proof of P=NP. Remark 61 (On Rank Definitions).The examples in §§20–22 were pedagogical and use a simple distinct-values notion of rank—the number of different outputs taken by the multilinear extension p:{0,1}d→Q. In contrast, all formal results and theorems elsewhere in this paper use SPDP-rank, an algebraic independence measure based on shifted partial derivatives. The earlier examples were included only for intuition; they do not contradict the later algebraic rank results. 152 31 Value-rank (pedagogical) In this section only, “rank” means the number of distinct values the multilinear extension p:{0,1}n→Ftakes on the Boolean cube: valrank(p) = |{p(a) : a∈ {0,1}n}|. This notion is for intuition and is unrelated to SPDP rank (Definition 11). 32 Barriers Revisited (Concise Addendum) Scope. Earlier parts introduce SPDP-rank and the three classical barriers. Here we only record the additional facts we actually use and point to the exact places where the full arguments live. •Full barrier proofs (relativization, natural proofs, algebrization): §2.4.1–§2.4.2 and Appendix C. •Extended/implementation details and comparisons: §26.3, §29.6, §29.8–§29.9. 32.1 25.1 What we record (without re-explaining) We use three facts: 1. Oracle invariance (method-level non-relativization). The SPDP matrix of a fixed polynomial pfis algebraic and unchanged by adding an oracle; thus any rank gap (exp vs poly) used as a witness persists under relativization. (Proofs: §2.4.1, App. A.1–A.4.) 2. Quantitative sparsity (non-naturality backbone). Low SPDP-rank functions form an exponentially tiny subset of all Boolean functions; PRG-style indistinguishability then rules out “usefulness.” (Proofs: §2.4.2, App. A.M, A.O.) 3. Algebrization note. The argument is inherently algebraic (polynomials + linear algebra over fields) and sits outside standard algebrizing templates. (Discussion/proofs: §2.4, App. A.3–A.4, §29.9.) 32.2 25.2 Relativization (method-level) Theorem 163 (Oracle invariance of SPDP-rank).For any oracle Oand Boolean fwith multilinear extension pf, SPDP-rankO(pf) = SPDP-rank(pf). Idea. The SPDP matrix uses only coefficients of pfand evaluations on {0,1}n; oracles change computation, not this algebraic object. (Complete proofs: §2.4.1, App. A.1–A.4.) 153