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

Towa d P=NP: An Obse e -Theo e ic Sepa a ion
ia SPDP Rank and a ZFC-Equi alen Founda ion
wi hin he N-F ame Model
Da en J. Edwa ds∗
Swansea Uni e si y
[email p o ec ed]
No embe 23, 2025
Abs ac
We p esen a sel -con ained sepa a ion amewo k o P s. NP buil in ZFC: (i) a
de e minis ic, adius-1compila ion om uni o m poly ime Tu ing compu a ion o local
sum-o -squa es (SoS) polynomials wi h polyloga i hmic con ex ual en anglemen wid h
(CEW), (ii) a o mal Wid h⇒Rank uppe bound o he esul ing SPDP ma ices a
ma ching pa ame e s (k, ℓ) = Θ(log n), (iii) an NP -side iden i y-mino lowe bound
in he same encoding, and (i ) a ank-mono one, ins ance-uni o m ex ac ion map
TΦ om he compiled P-side polynomials o he NP amily. Toge he hese yield a
con adic ion unde P=NP . We emphasize ha ou con ibu ion is a comple e ZFC
a chi ec u e wi h ull p oo s o he p imi i es and composi ion; communi y e i ica ion
(and ideally machine-checked Lean o maliza ion) emains u u e wo k.
The analysis de elops a co espondence be ween Con ex ual En anglemen Wid h
(CEW)—a quan i a i e desc ip o o compu a ional con ex uali y—and SPDP ank,
yielding a uni ied c i e ion o complexi y sepa a ion. We p o e ha bounded-CEW ob-
se e s co espond o polynomial- ank compu a ions ( he class P), whe eas unbounded
CEW co esponds o he class NP. This es ablishes ha he exponen ial SPDP ank o
#3SAT and ela ed ha d languages implies P =NP wi hin he s anda d amewo k o
complexi y heo y.
Key echnical componen s include: (1) cons uc i e lowe bounds on SPDP ank
de i ed om Ramanujan–Tsei in expande amilies; (2) non-ci cula educ ion om
Tu ing-machine compu a ion o low- ank polynomial e alua ion; (3) a codimension-
collapse lemma ensu ing ha ank ampli ica ion canno occu wi hin polynomial e-
sou ces; and (4) p oo o ba ie immuni y agains ela i iza ion, na u al p oo s, and
algeb iza ion. Toge he , hese esul s yield a ma hema ically sel -con ained p oo a chi-
ec u e ha econciles classical complexi y heo y wi h an obse e - heo e ic model o
∗The enhanced amewo k p o ides bo h classical complexi y heo y sepa a ion and epis emic in e p e-
a ion ia Con ex ual En anglemen Wid h (CEW)-bounded obse e s. Fo a deepe explo a ion o he
N-F ame model and obse e -cen ic app oach, see Edwa ds’ o hcoming wo k “The Obse e Cen ic Uni-
e se, Quan um Mechanics, and he Pa h o AGI Alignmen ” (Palg a e, 2026).
1
compu a ion, in which esou ce-bounded obse e s a e cha ac e ized by hei algeb aic
in o ma ion wid h.
P oo A chi ec u e. This pape p o ides a cons uc i e, ZFC- o malizable sepa a ion
o Pand NP ia he SPDP holog aphic amewo k. The a gumen p oceeds h ough (i) a
de e minis ic adius-1compila ion o all polynomial- ime DTMs o local SoS polynomials
o polylog CEW (Theo em 64), (ii) an NP-side iden i y-mino lowe bound es ablishing
exponen ial SPDP ank (Theo em 66), and (iii) a ank-mono one block-local educ ion om
P-compiled polynomials o NP ins ances (Theo em 143). All s eps a e de inable in i s -o de
a i hme ic and e i iable in Lean (Appendix G).
Con en s
1 In oduc ion: Dual App oaches o P s NP 8
1.1 Fo malP elimina ies ............................... 13
1.2 Con ex ual En anglemen Wid h (CEW): de ini ion and p o ed p ope ies . 13
1.3 Founda ional De ini ions (ZFC-Le el P imi i es) . . . . . . . . . . . . . . . . 17
2 Polynomial Wid h⇒Rank ia Cons an -Type P o iles 19
2.1 Se ing and assump ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Canonical windows, no mal o ms, and p o iles . . . . . . . . . . . . . . . . . 19
2.3 Polynomial Wid h⇒Rank ............................ 23
2.4 Classical B idge: Equi alence o S anda d Complexi y Theo y . . . . . . . . 25
2.5 The Obse e -Theo e ic F amewo k . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Comp ehensi e Ve i ica ion A chi ec u e . . . . . . . . . . . . . . . . . . . . 29
2.7 KeyVisualDiag ams............................... 31
3 Technical Founda ions and Algo i hmic De ails 31
3.1 P–Cha ac e iza ion ia SPDP Rank (B anching-P og am Rou e) . . . . . . . 31
3.2 Low- ank ⇒P (De e minis ic In e pola ion Algo i hm) [Op ional] . . . . . . 36
3.3 B idge Be ween Pa ial-De i a i e and SPDP Rank . . . . . . . . . . . . . . 38
3.3.1 Comple e B idge P oo . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Ba ie T anscendence A gumen s . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Rela i iza ion Ba ie — Comple e P oo . . . . . . . . . . . . . . . . 39
3.4.2 Na u al P oo s Ba ie — Algeb aic Non-Na u ali y (Comple e) . . . 40
3.5 Non–Dependence on a Global B1–B2 (Cla i ica ion o Scope) . . . . . . . . . 42
3.6 Uni o m Mono onici y o All De i a i e O de s . . . . . . . . . . . . . . . . 44
3.7 De e minis ic, Polynomial-Time Cons uc ion o w∈V⊥
n........... 45
3.8 Na u al-P oo s Ba ie Remo ed Uncondi ionally . . . . . . . . . . . . . . . 47
3.9 Pu ingI AllToge he .............................. 50
4 No e on Lean Fo maliza ion and Comple ion 50
2
5 Obse e Model: CEW-Bounded Compu a ion 50
5.1 Obse e ame and CEW . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2 F omSPDP ank oCEW............................ 51
5.3 Epis emic complexi y classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4 Obse e esou ce sepa a ion and Epis emicP ⊊Epis emicNP ........ 53
6 The Obse e –Classical B idge: Fo mal Equi alence o Compu a ional
F amewo ks 53
6.1 Resou ce-Bounded Sepa a ion (Fo mal S a emen ) . . . . . . . . . . . . . . . 53
6.2 SPDP Theo y: Mul ilinea Founda ions (Wha We Ac ually Use) . . . . . . 54
6.3 Obse e –Classical B idge (Exac Compila ion) . . . . . . . . . . . . . . . . 54
6.4 Ma hema ical Soundness: Global Dual and Non-Ci cula i y . . . . . . . . . . 55
7 Epis emic Complexi y Classes and he Obse e Hie a chy 55
7.1 Obse e sandCEW ............................... 56
7.2 Epis emic classes (de ini ions ma ched o classical ones) . . . . . . . . . . . . 56
7.3 Basic ac s and equi alences . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
7.4 Hie a chy and sepa a ion in he epis emic iew . . . . . . . . . . . . . . . . . 57
7.5 Wha wedono claim .............................. 57
8 SPDP Theo y and Sepa a ion F amewo k 57
8.1 SPDPasa ankmeasu e............................. 57
8.2 Uppe and lowe bounds (link o §2 and §6/§14) . . . . . . . . . . . . . . . . 58
8.3 Non-ci cula sepa a ion cons uc ion (link o §2.7, §2.8) . . . . . . . . . . . . 59
8.4 Wha SPDP con ibu es (scope and posi ioning) . . . . . . . . . . . . . . . . 59
9 Model-Exac TM→Polynomial A i hme iza ion and he P⇒poly-SPDP
Theo em 59
9.1 Encoding and polynomial cons uc ion . . . . . . . . . . . . . . . . . . . . . 60
9.2 Locali yandSPDP ows............................. 61
9.3 A global polynomial uppe bound on Γk,ℓ(PM,n)................ 62
9.4 Main heo em................................... 62
9.5 Empi ical Clues om E olu iona y Sea ch . . . . . . . . . . . . . . . . . . . 63
10 Exponen ial SPDP Rank o he Pe manen 64
10.1 A Shi ed/In e sec ion SPDP Lowe Bound wi h Explici Cons an . . . . . . 67
10.2 Disco e y o he Global God-Mo e . . . . . . . . . . . . . . . . . . . . . . . 70
10.3 Global P ojec ion (“God Mo e”): Iden i y Mino o Mk,0(pe mn)...... 71
11 In eg a ion and Ve i ica ion F amewo k 75
11.1 ZFC exp essibili y and conse a i i y . . . . . . . . . . . . . . . . . . . . . . 75
11.2 Obse e –classical b idge (bo h di ec ions) . . . . . . . . . . . . . . . . . . . 76
11.3 Main sepa a ion: composi ion o ea lie esul s . . . . . . . . . . . . . . . . . 77
11.4 Ba ie compa ibili y and e i ica ion summa y . . . . . . . . . . . . . . . . 78
3
12 Theo e ical Ad an ages o Obse e Model 79
12.1 Quan i ied soundness (compu e s. e i y) . . . . . . . . . . . . . . . . . . . 79
12.2Uni iedencapsula ion............................... 80
12.3Modula i y .................................... 80
12.4 Epis emic in e p e a ion ( ema k) . . . . . . . . . . . . . . . . . . . . . . . . 80
12.5Ex ensibili y( ema k) .............................. 80
13 Fo mal Equi alence, Assump ion In en o y, and Ve i ica ion Audi 80
13.1 Fo mal Equi alence Theo em . . . . . . . . . . . . . . . . . . . . . . . . . . 80
13.2 Assump ion In en o y (all p o ed ea lie ) . . . . . . . . . . . . . . . . . . . . 81
13.3 Ve i ica ion Audi (End- o-End) . . . . . . . . . . . . . . . . . . . . . . . . . 82
14 Examples o CEW Compu a ion 83
14.1 Se up and CEW con en ion . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
14.2Pa i y ....................................... 83
14.3AND........................................ 84
14.4Majo i y...................................... 84
14.5Takeaway ..................................... 84
15 The Pe manen Func ion and he #3SAT Cha ac e is ic Polynomial 85
15.1 The pe manen polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
15.2 The #3SAT cha ac e is ic polynomial . . . . . . . . . . . . . . . . . . . . . . 86
15.3 Consequences and posi ioning . . . . . . . . . . . . . . . . . . . . . . . . . . 88
16 Boolean Func ion Encoding 88
16.1 Boolean →mul ilinea in e pola ion . . . . . . . . . . . . . . . . . . . . . . . 89
16.2 Canonical encodings o SAT and #SAT . . . . . . . . . . . . . . . . . . . . 89
16.3 A no e on he pe manen (decision s. coun ing) . . . . . . . . . . . . . . . . 89
17 Exponen ial Lowe Bound o #3SAT 90
17.1 Ramanujan–Tsei in SPDP lowe bound (p o ed) . . . . . . . . . . . . . . . . 90
17.2 N-F ame Lag angian: analy ic e o mula ion o he ha d bound . . . . . . . 95
17.3 #3SAT SPDP lowe bound (di ec combina o ial p oo ) . . . . . . . . . . . . 96
17.4 En opy/weigh no e (suppo o andom pa i ioning) . . . . . . . . . . . . 97
18 The 3-SAT “God Mo e”: om ha d ins ances o sepa a ion ( ull p oo s) 97
18.1 Non-ci cula a chi ec u e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
18.2 3-SAT as he ha d language . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
18.3 Two algeb aic ac s used o padding . . . . . . . . . . . . . . . . . . . . . . 99
18.4 No-padding ( obus ness o s anda d dummy paddings) . . . . . . . . . . . . 99
18.5 Round- ip padding equi alence (sa e NC0augmen a ion) . . . . . . . . . . . 100
18.6Sepa a ion..................................... 101
4
19 CNF-SAT as an Al e na i e Ha d Language (Ze o-Tes Cons uc ion) 101
19.1 CNF →polynomial: he ze o– es . . . . . . . . . . . . . . . . . . . . . . . . 101
19.2 Combina o ics o monomials and linea independence . . . . . . . . . . . . . 102
19.3 Exponen ial SPDP ank (global) . . . . . . . . . . . . . . . . . . . . . . . . . 103
19.4 Ha d language ia ze o es . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
19.5Pu poseandplacemen .............................. 104
20 Fo mal Comple ion o he “God Mo e” 104
20.1 Uni o m codimension collapse o all P . . . . . . . . . . . . . . . . . . . . . 104
20.2 A ma ching NP lowe bound unde he same es ic ion . . . . . . . . . . . . 105
20.3 Sepa a ion ia an annihila o o he P-side span . . . . . . . . . . . . . . . . 107
20.4 CEW as he seman ic w appe (and i s equi alence) . . . . . . . . . . . . . . 108
20.5 Pa ame e choices and ield no es . . . . . . . . . . . . . . . . . . . . . . . . 108
20.6 Codimension Collapse Lemma ( ully de ailed p oo ) . . . . . . . . . . . . . . 109
20.7 De e minis ic swi ching and explici uni e sal es ic ion . . . . . . . . . . . 110
20.7.1 De e minis ic Swi ching Lemma ( ull p oo ) . . . . . . . . . . . . . . 111
20.7.2 Sho seed and PRG e o ( ull s a emen and p oo ) . . . . . . . . . 111
20.7.3 Tableau- o-wid h-5 ansla ion ( ull p oo ) . . . . . . . . . . . . . . . 112
20.7.4 Uni o m collapse (consequence) . . . . . . . . . . . . . . . . . . . . . 112
20.8 SPDP Res ic ion Lemma (Kayal–Saha– ype wi ness) — ull p oo . . . . . . 112
20.9 Uni o m SPDP es ic ion o NP (explici cons an s; ull p oo ) . . . . . . . 114
20.10Cons uc i e Ve i iabili y o SPDP Rank . . . . . . . . . . . . . . . . . . . . 115
20.11Ve i ie No maliza ion and Ins ance-Uni o m Ex ac ion . . . . . . . . . . . . 117
21 Complexi y Class Sepa a ions 119
21.1 P has polynomial SPDP ank . . . . . . . . . . . . . . . . . . . . . . . . . . 119
21.2 Obse e –SPDP equi alence . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
21.3 B anching-p og ams h ough he obse e lens . . . . . . . . . . . . . . . . . 120
21.4 Compu a ional ha dness o CEW . . . . . . . . . . . . . . . . . . . . . . . . 121
21.5 Supe polynomial ank gap inside NP . . . . . . . . . . . . . . . . . . . . . . 121
21.6 Final heo em: CEW collapse implies P=NP ................. 121
21.7 Classical co espondence (op ional summa y) . . . . . . . . . . . . . . . . . . 121
22 Main Sepa a ion Theo em 122
22.1Ba ie Immuni y................................. 122
22.2 F om Rank Gap o Complexi y Sepa a ion . . . . . . . . . . . . . . . . . . . 123
22.3TheExponen ialGap............................... 123
22.4 In eg a ion wi h he Lag angian and PAC F amewo ks . . . . . . . . . . . . 123
22.4.1 SPDP–Lag angian co espondence (seman ic laye ) . . . . . . . . . . 124
22.4.2 Posi i e Algeb aic Compila ion (cons uc i e laye ) . . . . . . . . . . 124
22.4.3 T i-Aspec comple ion . . . . . . . . . . . . . . . . . . . . . . . . . . 124
22.5 Classical Co espondence and ZFC In e p e a ion (op ional) . . . . . . . . . 125
5

23 Holog aphic P inciple and he God-Mo e Comple ion 125
23.1 Holog aphic Uppe -Bound P inciple . . . . . . . . . . . . . . . . . . . . . . . 125
23.2 Why Holog aphy Closes he God-Mo e . . . . . . . . . . . . . . . . . . . . . 127
23.3 Geome ic In e p e a ion o he Holog aphic Sepa a ion . . . . . . . . . . . . 128
23.4 Holog aphic Locali y and he God-Mo e Pa h . . . . . . . . . . . . . . . . . 130
23.5 G aphical Summa y: The Holog aphic Rank Gap . . . . . . . . . . . . . . . 131
23.6 De e minis ic Compila ion and he Global God-Mo e . . . . . . . . . . . . . 131
23.7 Concep ual Syn hesis: F om Holog aphy o he Global God-Mo e . . . . . . 131
23.8 Connec ion o he N-F ame Lag angian and PAC–Expande Geome y . . . 134
24 Global God Mo e and Uncondi ional Sepa a ion 135
25 Holog aphic In a iance and he Global God-Mo e 138
25.1 P esen a ion s. Algeb a (Gauge In a iance) . . . . . . . . . . . . . . . . . . 138
25.2 Uni o mi y o he P-Side Pipeline . . . . . . . . . . . . . . . . . . . . . . . . 138
25.3 Robus , Basis-In a ian Ce i ica es . . . . . . . . . . . . . . . . . . . . . . . 139
26 Fo mal P oo A chi ec u e 140
26.1 SPDP De ini ion and Wid h⇒RankTheo em ................. 140
26.2 NP-Side Lowe Bound (Iden i y Mino ) . . . . . . . . . . . . . . . . . . . . . 141
26.3 De e minis ic Compile and CEW Bound . . . . . . . . . . . . . . . . . . . . 141
26.4 In a iance and Mono onici y Lemmas . . . . . . . . . . . . . . . . . . . . . . 142
26.5 Ins ance-Uni o m Ex ac ion TΦ......................... 142
26.6 Clause-Shee Sepa abili y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
26.7 Final Sepa a ion (Global God-Mo e Theo em) . . . . . . . . . . . . . . . . . 143
26.8Rema ks...................................... 144
27 Global God-Mo e In eg a ion and Uncondi ional Sepa a ion 144
28 Ba ie Analysis: Rela i iza ion, Na u al P oo s, and Algeb iza ion 146
28.1 Rela i iza ion: O acle-In a iance o SPDP Rank . . . . . . . . . . . . . . . . 146
28.2 Na u al P oo s: Non-La geness o High-SPDP P ope y . . . . . . . . . . . . 147
28.3Algeb iza ion ................................... 148
29 Pe manen Polynomial: De ailed Cons uc ion 149
29.1 Pe mu a ion-Based De ini ion . . . . . . . . . . . . . . . . . . . . . . . . . . 149
29.2 Pe manen Rank: Many Dis inc E alua ions . . . . . . . . . . . . . . . . . . 149
30 Conc e e Rank (Dis inc -Value) Calcula ions on {0,1}d150
30.1Elemen a yFunc ions............................... 150
30.2Symme icFunc ions............................... 150
30.3 Ma ix Func ions (2×2and 3×3) ....................... 151
30.4 Simple G aph P ope ies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
30.5 “Sepa a ion” Examples (unde dis inc - alues ank) . . . . . . . . . . . . . . 151
30.6 Rank G ow h Pa e ns (Co ec ed Table) . . . . . . . . . . . . . . . . . . . . 152
30.7 B idge No e (on Rank No ions) . . . . . . . . . . . . . . . . . . . . . . . . . 152
6
31 Value- ank (pedagogical) 153
32 Ba ie s Re isi ed (Concise Addendum) 153
32.1 25.1 Wha we eco d (wi hou e-explaining) . . . . . . . . . . . . . . . . . . 153
32.2 25.2 Rela i iza ion (me hod-le el) . . . . . . . . . . . . . . . . . . . . . . . . 153
32.3 25.3 Na u al P oo s (quan i a i e non-na u ali y) . . . . . . . . . . . . . . . 154
32.425.4Algeb iza ion................................. 155
32.5 25.5 Lean e e ences (single sou ce o u h) . . . . . . . . . . . . . . . . . . 155
32.6 25.6 Quick compa ison ( eade aid) . . . . . . . . . . . . . . . . . . . . . . . 155
33 The Big Pic u e 156
33.1 Wha Makes This P oo Wo k . . . . . . . . . . . . . . . . . . . . . . . . . . 156
33.2 Impac on Complexi y Theo y . . . . . . . . . . . . . . . . . . . . . . . . . . 156
33.3 Philosophical Implica ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
34 Discussion and Ou look 157
34.1 SPDP Holog aphy as a Cons uc i e Sepa a ion . . . . . . . . . . . . . . . . 157
34.2 Rela ion o he N-F ame Lag angian . . . . . . . . . . . . . . . . . . . . . . 157
34.3 Implica ions o Fo mal Ve i ica ion . . . . . . . . . . . . . . . . . . . . . . . 158
34.4 Nex S eps and Open Ques ions . . . . . . . . . . . . . . . . . . . . . . . . . 158
34.5 Philosophical Signi icance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
35 Conclusion 159
.1 De ailed P oo o Pe manen Exponen ial SPDP-Rank . . . . . . . . . . . . 166
A S o johann-Wiedemann Rank Algo i hm 168
B P obabili y Bounds 169
B.1 Fo malS a emen ................................. 170
B.2 S ep-by-S ep Analy ic P oo . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
C Empi ical Valida ion o P→poly-SPDP and Diagonal Ve i ie 175
C.1 Signi icance o Empi ical Valida ion . . . . . . . . . . . . . . . . . . . . . . . 178
C.2 Empi ical Valida ion F amewo k . . . . . . . . . . . . . . . . . . . . . . . . . 178
C.2.1 Empi ical Assump ions . . . . . . . . . . . . . . . . . . . . . . . . . . 178
C.2.2 Jus i ica ion and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 179
C.2.3 Da a Sou ces and Valida ion . . . . . . . . . . . . . . . . . . . . . . . 179
C.2.4 Key Lemmas Using These Bounds . . . . . . . . . . . . . . . . . . . . 180
C.3 Ci cui Families and Collapse Summa y . . . . . . . . . . . . . . . . . . . . . 181
C.4 Collapse Resul s and Wi ness Selec i i y . . . . . . . . . . . . . . . . . . . . 183
C.5 Diagonal Failu e Cases and Selec i i y . . . . . . . . . . . . . . . . . . . . . 183
C.6 Run ime Scaling o Diagonal Failu e Cases . . . . . . . . . . . . . . . . . . 185
C.7 Symbolic SPDP Rank Selec i i y . . . . . . . . . . . . . . . . . . . . . . . . 187
C.8 Empi ical Valida ion o he God Mo e ia Nullspace Collapse . . . . . . . . 187
C.8.1 Da a Sou ce and Nullspace Ve i ica ion . . . . . . . . . . . . . . . . . 191
C.9 Empi ical Valida ion Summa y . . . . . . . . . . . . . . . . . . . . . . . . . 191
7
C.10Empi icalConclusion............................... 192
C.11 SPDP Rank Scaling and Visualiza ion . . . . . . . . . . . . . . . . . . . . . 192
D SPDP, CEW, In a iance, Lowe Bound, and Con adic ion 194
D.1 Iden i y-Mino Lowe Bound (Explici Spli e ) . . . . . . . . . . . . . . . . 196
E Fo mal De ini ions (ZFC-Le el P imi i es) 198
E.1 SPDP Ma ix and Rank Measu e . . . . . . . . . . . . . . . . . . . . . . . . 198
E.2 Con ex ual En anglemen Wid h (CEW) . . . . . . . . . . . . . . . . . . . . 199
E.3 So ing-Ne wo k Compile P imi i e . . . . . . . . . . . . . . . . . . . . . . . 199
E.4 Wid h ⇒RankLemma.............................. 199
E.5 Mono onici yLemmas .............................. 200
F NP Lowe Bound a Ma ching Pa ame e s 201
G Comple e Lean Skele on o Implemen a ion 202
G.1 P ac ical Nex S eps o Implemen e s . . . . . . . . . . . . . . . . . . . . . 203
H Compu a ional E idence o he Uni o m Compile Hypo hesis 204
H.1 Expe imen alSe up................................ 204
H.2 Resul sSumma y................................. 204
H.3 In e p e a ion................................... 205
H.4 Da a and Rep oducibili y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
H.5 Conclusion..................................... 206
I In e nal Consis ency: Symbol Table 206
I.1 Co e SPDP F amewo k No a ion . . . . . . . . . . . . . . . . . . . . . . . . 206
I.2 Special Func ions and Cons uc ions . . . . . . . . . . . . . . . . . . . . . . 206
I.3 Final Me a Laye : ZFC Fo malizabili y and Lean Embedding . . . . . . . . . 207
1 In oduc ion: Dual App oaches o P s NP
The ques ion o whe he P = NP emains he cen al open p oblem in heo e ical compu e
science [1, 2]. While classically ph ased in syn ac ic e ms—does e e y e icien ly e i iable
language admi an e icien decision p ocedu e?— his aming conceals deepe epis emic
and s uc u al ques ions. T adi ional app oaches ea compu a ional ha dness as a s a ic
p ope y o ma hema ical objec s (languages, unc ions, ci cui s), ye decades o s alled
p og ess sugges ha his ”objec -cen ic” pe spec i e may miss a c ucial dimension: he
ole o in e ence i sel .
A i s co e, compu a ion is an in e en ial p ocess pe o med by an obse e bounded
by in o ma ional and physical cons ain s. E e y algo i hm, ci cui , o p oo p ocedu e
can be iewed as a channel h ough which an obse e upda es in e nal in o ma ion s a es
in esponse o ex e nal que ies. F om his s andpoin , he complexi y o a p oblem is no
me ely a p ope y o he p oblem ins ance bu a unc ion o he obse e ’s abili y o comp ess,
p edic , and ans o m s uc u ed in o ma ion unde limi ed esou ces. This mo i a es an
8
obse e - heo e ic e o mula ion o complexi y heo y—one ha desc ibes compu a ional
classes in e ms o he in o ma ional geome y o in e ence a he han he syn ac ic leng h
o p oo s o he ga e coun o ci cui s.
We de elop his pe spec i e h ough a uni ied algeb aic and geome ic amewo k g ounded
in wo complemen a y measu es: he Shi ed Pa ial De i a i e Polynomial (SPDP) ank and
Con ex ual En anglemen Wid h (CEW). SPDP ank cap u es he algeb aic g ow h o mul-
ilinea polynomial ep esen a ions o Boolean unc ions and p o ides a cons uc i e measu e
o exp essi e powe . CEW, in u n, quan i ies he deg ee o con ex ual in e dependence an
obse e mus main ain o in e o e i y compu a ional ou comes. Toge he , hey yield
a dual desc ip ion o compu a ion: algeb aic complexi y on he one hand and in e en ial
con ex uali y on he o he .
Wi hin his amewo k, we show ha polynomial- ime compu a ion co esponds o ob-
se e s o bounded CEW, whose algeb aic ep esen a ions exhibi only polynomial SPDP
ank. NP-comple e p oblems, con e sely, equi e unbounded con ex ual en anglemen , p o-
ducing exponen ial SPDP ank. This co espondence allows a di ec and cons uc i e p oo
ha no polynomial- ime obse e can eplica e he in e en ial s uc u e o NP-comple e e -
i ica ion. In pa icula , we de i e explici Boolean amilies—buil om Ramanujan–Tsei in
expande cons uc ions—whose SPDP ank g ows exponen ially while p ese ing bounded
ci cui dep h and cons an a i y. These cons uc ions p o ide he i s ully algeb aic ou e
o exponen ial lowe bounds wi hou appealing o o acle o andom- es ic ion a gumen s.
The p oo a chi ec u e p oceeds h ough ou laye s. Fi s , we es ablish analy ic domi-
nance lemmas showing ha exponen ial- ank g ow h asymp o ically exceeds any polynomial
bound. Second, we o malize es ic ion and codimension-collapse lemmas gua an eeing ha
ank ampli ica ion canno occu wi hin polynomial esou ce limi s. Thi d, we link SPDP
ank o con ex ual in e ence ia CEW, showing ha bounded-wid h obse e s co espond
p ecisely o polynomial- ank unc ions. Finally, we demons a e ha his s uc u e emains
immune o known ba ie s such as ela i iza ion, na u al p oo s, and algeb iza ion, comple -
ing a ma hema ically sel -con ained sepa a ion.
Beyond esol ing he P =NP ques ion in his amewo k, he esul s sugges a deepe
connec ion be ween compu a ion, in o ma ion, and physical in e ence. By cha ac e izing
compu a ional ha dness as a p ope y o epis emic geome y— he shape o in o ma ion low
a ailable o an obse e — he heo y uni ies classical complexi y, algeb aic geome y, and
he physics o obse a ion unde a single p inciple: ha he limi s o e icien compu a ion
coincide wi h he limi s o bounded in e ence.
S a us. All p imi i es a e p o ed in ZFC a he s a ed gene ali y. We delibe a ely a oid
claims o consensus o inali y: accep ance o his p og am as a de ini i e p oo o P=NP
es s on communi y sc u iny and (ideally) machine-checked e i ica ion.
The Global God-Mo e Gauge
To compa e P- and NP- amilies wi hin one s uc u al amewo k, we ix a canonical coo -
dina e sys em o all compiled compu a ions.
De ini ion 1 (Global God-Mo e Gauge).Aglobal gauge is a canonical diagonal basis Π+=
9
De ini ion 9 (Shi ed Pa ial Ma ix).The shi ed pa ial ma ix SPℓ(p, s) o polynomial
p, o de ℓ, and shi ec o shas en ies:
SPℓ(p, s)I,x =∂Ip(x+s)
whe e I anges o e index se s o size ℓ.
De ini ion 10 (Obse e F ame).An obse e ame is a iple F= (S, R, I)whe e S
is a s uc u ed objec , Ris a esolu ion class o algeb aic ope a ions, and Iis an in e ence
ope a o measu ing accessible o ms.
Table 1: Obse e F ame De ini ion
De ini ion A (Obse e F ame)
An obse e ame is a iple F= (S, R, I)consis ing o :
1. A s uc u ed objec S(e.g., a Boolean unc ion, polynomial, o CNF o mula);
2. A esolu ion class Ro admissible algeb aic ope a ions such as pa ial de i a i es,
low-deg ee shi s, and coo dina e p ojec ions ha gene a e obse able o ms om
S;
3. An in e ence ope a o I ha quan i ies he dimensionali y o he span o o ms
accessible h ough R.
In his wo k, he esolu ion class Ris ixed as he se o pa ial de i a i es, low-deg ee
shi s, and coo dina e p ojec ions, while he in e ence ope a o Iis ins an ia ed as he
Shi ed Pa ial De i a i e Polynomial (SPDP) ank measu e. Fo gene ali y, howe e ,
we keep Iabs ac h oughou mos o he heo e ical de elopmen .
In he N-F ame model, he e m “N” deno es na u al selec ion ac ing o e he land-
scape o compu a ional o ms, while “F ame” e e s o he obse e ame F= (S, R, I) ha
bounds wha can be in e ed. This iewpoin ein e p e s compu a ional complexi y as a
heo y o obse e -bounded in e ence. Fo a philosophical and geome ic in e p e a ion o
his in e ence-bounda y app oach, see Edwa ds’ wo k on N-F ame ne wo king dynamics o
conscious obse e -sel agen s [3] and he comp ehensi e ea men in [4].
This wo k is mo i a ed by he N-F ame model, which ein e p e s compu a ional com-
plexi y as a heo y o obse e -bounded in e ence. In he N-F ame iew, complexi y classes
a e de ined no solely by exis en ial quan i ie s o e Tu ing machines, bu by he o mal
s uc u e o wha can be e i ied using ini e algeb aic c i e ia. Wi hin his amewo k, alge-
b aic collapse (o non-collapse) becomes a model o in e en ial cu a u e: a measu e o wha
he obse e can ”see.” The key insigh is ha ha dness may eme ge no om he pla onic
non-exis ence o small ci cui s, bu om he seman ic bounda y o wha bounded obse e s
can comp ess and e i y.
16

No a ion
Th oughou his pape , we use he ollowing no a ion:
•CEW( )– Con ex ual En anglemen Wid h o unc ion
•CEWlimi (n)– Maximum CEW on inpu s o leng h n
• ks(p)o SPDP- ank(p)– SPDP- ank o polynomial p
•Mℓ,p – Shi ed pa ial de i a i e ma ix a o de ℓ
•ρs∗– Uni e sal es ic ion map wi h seed s∗
•e ( )– E alua ion ec o o unc ion
No e: We use CEWlimi uni o mly h oughou ( eplacing ad-hoc names like w(n)).
1.3 Founda ional De ini ions (ZFC-Le el P imi i es)
De ini ion 11 (Shi ed–Pa ial–De i a i e ank).Le p∈F[x1, . . . , xn]and k, ℓ ≥0. De ine
Γk,ℓ(p) := dimFSpan{m·∂Sp|S⊆[n],|S|=k, m monomial,deg(m)≤ℓ}.
Equi alen ly, o m he SPDP ma ix Mk,ℓ(p)whose ows a e he coe icien ec o s o all
m·∂Spwi h |S|=kand deg(m)≤ℓ; hen Γk,ℓ(p) = ankFMk,ℓ(p).
Explici ma ix cons uc ion. Fo comple e o mal speci ica ion, he SPDP ma ix
Mk,ℓ(p)has:
•Row indices: Pai s (S, m)whe e S⊆[n]wi h |S|=kand mis a monomial wi h
deg m≤ℓ.
•Column indices: All monomials in he s anda d monomial basis o F[x1, . . . , xn].
•En y a (S, m): The coe icien ec o o m·∂Spwhen expanded in he monomial
basis.
In ZFC e ms: Mk,ℓ(p)is a ini e ma ix wi h en ies in F, and i s ank is compu ed ia
Gaussian elimina ion (o any equi alen algo i hm decidable in ZFC).
CEW scale. Ou de e minis ic compile has pe -access CEW =O(log log N)and, ac oss
any poly(n)accesses, global CEW ≤C(log n)c o absolu e cons an s C, c > 0. We he e o e
ins an ia e R:= C(log n)cin he Wid h⇒Rank bound below (Lemma 8).
Lemma 8 (CEW bound o he so ing-ne wo k compile ).Le NNbe a Ba che odd–e en
me ge so ing ne wo k on Nwi es, ealized by adius-1compa a o iles in he holog aphic
compile . Suppose each p imi i e ile ouches a mos b∈Nblock in e aces and each
17
compa a o in ol es a mos ∆∈Nsuch iles. Then o e e y ime s ep lying inside a
compa a o laye o NNwe ha e
CEW( )≤2b∆.
I he ag/upda e phases be ween compa a o laye s a e implemen ed by adius-1NC1ci cui s
o dep h O(log log N) ouching a mos c0in e aces pe laye , hen he e is a cons an C > 0
such ha o all we ha e
CEW( )≤Clog log N.
In pa icula , ac oss any polynomial numbe o accesses he compiled p og am sa is ies CEW(p)≤
C(log N)c o some absolu e cons an s C, c > 0.
P oo . Fix a compa a o laye Lin he so ing ne wo k and conside an a bi a y e ical cu
h ough he wi e a ay (equi alen ly, a pa i ion o he wi es in o le and igh se s). In a
Ba che odd–e en me ge ne wo k he compa a o s in each laye ac on disjoin adjacen wi e
pai s. Consequen ly, any such cu in e sec s he “le ” endpoin o a mos one compa a o
and he “ igh ” endpoin o a mos one compa a o in ha laye . Thus he cu mee s a
mos 2compa a o s in L.
By assump ion each compa a o is implemen ed by a mos ∆p imi i e iles, and each
ile ouches a mos bblock in e aces in he diagonal basis. The e o e, a he ime s ep
co esponding o he execu ion o his laye , he o al numbe o in e aces ouched ac oss
he cu is a mos
2·∆·b= 2b∆.
Since his holds o e e y e ical cu , we ob ain CEW( )≤2b∆on compa a o laye s.
Now conside a ag/upda e phase implemen ed by a adius-1NC1ci cui o dep h
O(log log N). Each ga e in such a ci cui ac s on a cons an -size neighbo hood o wi es
and hence, in he diagonal basis, ouches a mos b′=O(1) in e aces. A each dep h-d
laye o he ci cui , he an-ou is bounded and he numbe o simul aneously ac i e ga es
in e sec ing any cu is a mos a cons an c0(depending only on he compile , no on N).
Thus o e e y ime s ep inside a ag/upda e phase we ha e
CEW( )≤c0b′≤C0
o some absolu e cons an C0. The o al numbe o ag/upda e laye s pe access is O(log log N),
bu CEW( )is de ined as a maximum o e ime, no a sum, so we s ill ha e CEW( )≤C0
on hose phases.
Combining he wo cases, we ob ain a uni o m bound
CEW( )≤C1
o all ime s eps wi hin a single access, whe e C1depends only on b, ∆and he NC1im-
plemen a ion. Finally, no e ha composing a polynomial numbe o such accesses p ese es
a polyloga i hmic bound on CEW; mo e p ecisely, he e exis cons an s C, c > 0such ha
CEW(p)≤C(log N)c o he compiled polynomial p. This is he claimed bound.
18
2 Polynomial Wid h⇒Rank ia Cons an -Type P o iles
2.1 Se ing and assump ions
We wo k wi h he de e minis ic holog aphic compile in he diagonal basis wi h Π+=A,
adius 1, and an ins ance-uni o m access schedule. The quan i a i e assump ions used he e
a e:
(A1) Radius-1 locali y. Each p imi i e ope a ion (ga e/ ile) ouches a mos b∈Nblock
in e aces, whe e b=O(1) depends only on he compile .
(A2) Fini e local alphabe . In he diagonal basis wi h Π+=A, he e ec o a p imi i e
ope a ion on a single in e ace is de e mined by a local ype τ∈Σ; he alphabe size
|Σ|=S=O(1) is an absolu e cons an (e.g., compa a o ole, wi e pa i y, SoS ile
ole).
(A3) CEW bound. A e e y s ep, a mos Rin e aces a e li e (Con ex ual En anglemen
Wid h), wi h R=C(log n)c o absolu e cons an s C, c > 0.
(A4) SPDP pa ame e s. We use de i a i e o de kand deg ee gua d ℓwi h k, ℓ =
Θ(log n).
All hidden cons an s depend only on he compile and no on n, k, ℓ.
2.2 Canonical windows, no mal o ms, and p o iles
Aleng h-kwindow is a sequence o ksuccessi e di ec ional de i a i es applied o he compiled
p og am. We pass o canonical ep esen a i es ia he ollowing ules.
(C1) Commu a ion on disjoin suppo . I wo de i a i e s eps ac on disjoin in e ace
se s, hei o de is imma e ial; windows di e ing only by commu ing such s eps a e
iden i ied.
(C2) Local no mal o m ( igo ous). The local ype upda es a a ixed in e ace gene a e
a ini e monoid Mo bounded exponen m=O(1) o (equi alen ly o ou pu poses)
admi a ini e, leng h-dec easing ew i e sys em ha is con luen and e mina ing in
he diagonal basis. In ei he case, e e y local upda e wo d has a unique no mal o m
o leng h a mos q=O(1), depending only on he compile .
Rema k. Local upda es ac in he ini e ans o ma ion monoid on he ini e se Σ. Thus
any local wo d educes o a simple pa h o leng h a mos |Σ|−1, yielding q≤ |Σ|−1.
Fo a canonical window, each li e in e ace eexpe iences a (possibly emp y) sequence o
local- ype changes o leng h a mos q, d awn om he ini e se Σ≤q:=Sq
j=0 Σj.In e ace
iden i ies a e no eco ded:
De ini ion 12 (In e ace-anonymous p o ile).The p o ile o a canonical window is he his-
og am h: Σ≤q→N ha coun s, o each local ype wo d σ∈Σ≤q, he numbe o li e
in e aces whose local no mal o m equals σ. Thus Pσh(σ)≤R.
19
Lemma 9 (Pe mu a ion-in a iance wi hin blocks).I wo canonical windows di e only by
a pe mu a ion o in e ace iden i ies wi hin he same block pa i ion, hen hei SPDP ow
se s a e ela ed by le / igh mul iplica ion wi h block-diagonal in e ible ma ices (depending
only on he pe mu a ion), hence hey con ibu e he same ank. Consequen ly, SPDP uppe
bounds depend only on he p o ile his og am h om De ini ion 12.
P oo . Wi hin a block, pe mu ing in e ace coo dina es co esponds o applying a ixed pe -
mu a ion ma ix on he le / igh o he local e alua ion/de i a i e enso s. The global
SPDP ma ices a e buil om blockwise Kha i–Rao / K onecke combina ions o hese lo-
cal pieces; pe mu a ions ac as block-diagonal change-o -basis ma ices ha a e in e ible.
Rank is in a ian unde in e ible le / igh mul iplica ions, so only he mul ise (his og am)
o local wo ds ma e s.
Lemma 10 (Cons an local change budge ).Unde (A1) and (C2), each li e in e ace
unde goes a mos q=O(1) local ype changes in any canonical window, wi h qindependen
o n, k, ℓ.
P oo . By (A1), only a cons an -size neighbo hood N(e)o iles can a ec in e ace e. In
he diagonal basis, each ile induces a gene a o o he ini e local monoid M; by (C2), e e y
p oduc educes o a unique no mal o m o leng h a mos q=O(1). Hence he numbe o
e ec i e local ype changes a eis bounded by q.
Lemma 11 (Cons an - ype p o ile bound).Le S′:=|Σ≤q|=O(1). Unde (A1)–(A3) and
(C1),(C2), he numbe o dis inc p o iles ealizable by any canonical window is a mos
#P o iles ≤qR +S′
S′=RO(1).
In pa icula , his bound is independen o k.
P oo . By Lemma 10 each li e in e ace con ibu es a mos qlocal changes in no mal o m,
so he o al mass Pσh(σ)is a mos qR ac oss all li e in e aces. (Fine accoun ing shows
Pσh(σ)≤Ri each in e ace con ibu es a mos one nonemp y wo d, bu we uni o mly
ake he sa e bound ≤qR h oughou o a oid case-spli ing; since q=O(1) bo h yield
RO(1).) A p o ile is exac ly a weak composi ion o an in ege ≤qR in o S′=O(1) bins
(one bin pe σ∈Σ≤q). The numbe o such his og ams is he s a s-and-ba s coun qR+S′
S′,
which is RO(1) since q, S′a e absolu e cons an s. By Lemma 9, di e en assignmen s o he
same his og am o named in e aces do no c ea e new anks, so his coun is igh o SPDP
uppe bounds.
Lemma 12 (Coun ing in e ace-anonymous p o iles).Fix a ini e local alphabe Σwi h S=
|Σ|=O(1) and a cons an q∈N. Le Σ≤q=Sq
j=1 Σjdeno e he se o local ype wo ds o
leng h a mos q, and le M=|Σ≤q|. Then M=O(1), depending only on he compile .
Fo pa ame e s
R=C(log n)c, k =αlog n
wi h absolu e cons an s C, c, α > 0, he numbe o possible in e ace-anonymous k-s ep p o-
iles is a mos nO(1).
20
P oo . An in e ace-anonymous p o ile consis s o a sequence
h= (h1, . . . , hk), h : Σ≤q→N,
whe e each h is a his og am sa is ying
X
σ∈Σ≤q
h (σ)≤R.
The numbe o such his og ams h is bounded by he numbe o weak composi ions o an
in ege ≤Rin o Mpa s, namely
#{h } ≤ R+M
M.
Since Mis an absolu e cons an , we ha e
R+M
M≤(R+M)M≤(C′logcn)M= (log n)O(1).
Ak-s ep p o ile is a k- uple o such his og ams, so he o al numbe o p o iles is bounded
by R+M
Mk
≤(log n)O(1)k= (log n)O(k).
Wi h k=αlog nwe ob ain
(log n)O(k)= (log n)O(log n)=nO(1),
as claimed.
Lemma 13 (P o iles gene a e polylog-dimensional subspaces).Le pbe he compiled poly-
nomial in he diagonal basis, and ix pa ame e s k, ℓ = Θ(log n)and R=C(log n)cas in
Lemma 12. Fo each in e ace-anonymous k-s ep p o ile h he e exis s a linea subspace Vh
o he SPDP ow space such ha :
1. All SPDP ows co esponding o mixed pa ials ∂τpwi h |τ|=kand local ype s a is ics
ma ching hlie in Vh.
2. The dimension o Vhsa is ies
dim Vh≤(log n)O(1) ≤nO(1).
Consequen ly, i Hdeno es he se o all in e ace-anonymous p o iles, hen
Γk,ℓ(p)≤X
h∈H
dim Vh≤(log n)O(1) ·|H| =nO(1).
21

P oo . By adius-1locali y (Assump ion (A1)) and he ini e local alphabe (Assump ion (A2)),
he e ec o any q-s ep local e olu ion on a single in e ace is comple ely de e mined by he
ype wo d σ∈Σ≤q. Fo each σwe ob ain a ini e-dimensional subspace Wσo he ambien
SPDP ow space consis ing o all possible con ibu ions o a single in e ace o ype σac oss
all choices o mixed pa ials ∂τwi h |τ|=kand monomials uwi h deg u≤ℓ. The dimension
dim Wσis bounded by a cons an d0depending only on he compile .
Fix a p o ile hand le h(σ)deno e he o al mul iplici y o ype wo d σac oss he k ime
s eps. Because we a e wo king wi h in e ace-anonymous p o iles, in e aces o he same
ype a e indis inguishable: only he mul ise o ypes ma e s, no hei o de ing. The o al
con ibu ion o all in e aces o ype σ he e o e lies in he symme ic enso powe
Symh(σ)(Wσ),
whose dimension is gi en by
dim Symh(σ)(Wσ) = d0+h(σ)−1
h(σ)≤(d0+h(σ))d0−1.
Since Pσh(σ)≤kR =O((log n)1+c), each indi idual h(σ)is a mos O((log n)1+c), and
hus
dim Symh(σ)(Wσ)≤d0+O((log n)1+c)d0−1= (log n)O(1).
The ull con ibu ion o he p o ile his con ained in he enso p oduc
Vh⊆O
σ∈Σ≤q
Symh(σ)(Wσ).
The alphabe Σ≤qhas cons an size M=O(1), so he dimension o his enso p oduc is
bounded by
dim Vh≤Y
σ∈Σ≤q
dim Symh(σ)(Wσ)≤(log n)O(1)M= (log n)O(1).
This p o es (2). P ope y (1) holds by cons uc ion: o any SPDP ow whose local ype
e olu ion ma ches he p o ile h, each in e ace con ibu ion lies in he co esponding Wσ,
and he agg ega e o e all in e aces lies in he indica ed enso p oduc . Finally, combining
Lemma 12 (which gi es |H| ≤ nO(1)) wi h he bound on dim Vhyields
Γk,ℓ(p)≤X
h∈H
dim Vh≤(log n)O(1) ·|H| =nO(1),
as claimed.
Rema k 3.We do no ac ually need he p ecise polylog bound dim Vh≤(log n)O(1); i su ices
ha dim Vh≤nO(1).
Lemma 14 (Monomial/coo dina e budge ).Unde (A1) and wi h deg ee gua d ℓ=O(log n),
he numbe o admissible monomial/coo dina e choices pe ixed p o ile is nO(1).
22
P oo . Each SPDP ow co esponds o selec ing a mos ℓglobal a iables among nand
applying a mos ℓlocal de i a i e coo dina es, each suppo ed on a adius-1neighbo hood
(A1). Fo each j∈ {0, . . . , ℓ} he numbe o ways o pick jglobal a iables is n
j≤nj. Fo
each chosen a iable, he numbe o admissible local de i a i e coo dina es is bounded by
a compile -dependen cons an B=O(1) ( ini e local alphabe and adius-1suppo in he
diagonal basis). Hence
ℓ
X
j=0 n
jBj≤
ℓ
X
j=0
(Bn)j≤(ℓ+ 1) (Bn)ℓ=nO(ℓ)=nO(log n)=nO(1).
The hidden cons an depends only on Band he cons an implici in ℓ=O(log n).
2.3 Polynomial Wid h⇒Rank
Theo em 15 (Polynomial Wid h⇒Rank).Le pbe any P-compu able wo kload compiled
by he de e minis ic adius-1compile in he diagonal basis wi h Π+=A, unde (A1)–(A4).
Then o k, ℓ = Θ(log n)and R=C(log n)c,
Γk,ℓ(p)≤RO(1) ·nO(1) =nO(1).
P oo . Fix k, ℓ = Θ(log n)and le Wbe he se o canonical windows o leng h k, ob ained
ia (C1) and (C2). By Lemma 11, he se Ho in e ace-anonymous p o iles ealizable by
windows in Whas ca dinali y a mos Rα o an absolu e cons an α, independen o k.
Fo a p o ile his og am h∈ H, conside he SPDP subma ix consis ing o ows gene a ed
by windows wi h p o ile h. By Lemma 9, pe mu a ions o in e ace iden i ies wi hin blocks
ac by block-diagonal in e ible le / igh mul iplica ions on his subma ix and he e o e
do no change i s ank. I ollows ha he ank con ibu ion o all windows wi h p o ile h
is uppe -bounded by he numbe o admissible monomial/coo dina e choices consis en wi h
h. By Lemma 14, his quan i y is nO(1).
Summing o e p o iles yields he bound. By he cons an – ype p o ile bound (Lemma 11),
he numbe o in e ace–anonymous p o iles is RO(1). Fo each ixed p o ile, he monomial/-
coo dina e budge is nO(1) (Lemma 14). Hence Γk,ℓ(p)≤RO(1) ·nO(1). Since R=C(log n)c,
we ob ain Γk,ℓ(p)≤nO(1), es ablishing he claim.
Rema ks. (1) The key change ela i e o ea lie d a s is he in e ace-anonymous p o ile
(De ini ion 12) plus Lemma 9, which emo es an exponen ial dependence on R ha would
a ise om acking in e ace iden i ies. (2) The igo ized (C2) gua an ees a cons an no mal-
o m leng h qpe in e ace ia a ini e-monoid/ ew i ing a gumen , making he s a s-and-
ba s coun in Lemma 11 alid and independen o he window leng h k.
Consis ency wi h he holog aphic p inciple. In he diagonal basis wi h Π+=A,
(A1)–(A3) a e compile p ope ies; (C2) is a local algeb aic p ope y ( ini e monoid / e mi-
na ing ew i e sys em) induced by he same diagonaliza ion. Thus he p o ile bound RO(1) is
a s uc u al consequence o he compile and no o inpu size no choices o k, ℓ = Θ(log n).
23
Lemma 16 (Res ic ion mono onici y).Le ρbe a (block–local) es ic ion/iden i ica ion o
a iables and p′:= p↾ρ. Then o all k, ℓ,Γk,ℓ(p′)≤Γk,ℓ(p).
P oo . Le Rρ:F[x1, . . . , xN]→F[x′
1, . . . , x′
N′]be he linea subs i u ion map induced by
ρ. Di e en ia ion on ee a iables commu es wi h subs i u ion, hence o each gene a o
u∂τpo he SPDP ow–space we ha e Rρ(u∂τp) = u′∂τ′(p′) o sui able u′, τ′( a iables
elimina ed by ρ anish; cons an s mul iply coe icien s). The e o e Rρspan{u∂τp}con ains
span{u′∂τ′p′}. Since Rρis linea , dim span{u′∂τ′p′} ≤ dim span{u∂τp}, i.e. Γk,ℓ(p′)≤
Γk,ℓ(p).
Lemma 17 (Subma ix mono onici y).I M′is any subma ix o Mk,ℓ(p)ob ained by se-
lec ing a subse o ows and/o columns, hen ank(M′)≤Γk,ℓ(p).
P oo . Selec ing ows/columns co esponds o es ic ing he domain/codomain o he un-
de lying linea map, which canno inc ease ank.
Lemma 18 (A ine/basis in a iance).Le Φ : x7→ Ax +bwi h A∈GLN(F). Then
Γk,ℓ(p◦Φ) = Γk,ℓ(p) o all k, ℓ. Mo eo e , changing he monomial basis wi hin blocks
mul iplies Mk,ℓ(p)on he le / igh by block-diagonal in e ible ma ices, hence p ese es
ank.
P oo . By he mul i a ia e chain ule, ∂τ(p◦Φ) = P|σ|=|τ|ατ,σ (∂σp)◦Φ, whe e (ατ,σ)is he
in e ible mino map induced by Aon ∧|τ|FN. Mul iplying by all monomials uo deg ee
≤ℓand expanding in he monomial basis shows ha he SPDP ow–space o p◦Φis he
image o he SPDP ow–space o punde an in e ible linea ope a o (composi ion wi h
Φon coe icien s plus he mino map on pa ials). Dimensions a e equal. The Π+map ac s
block-locally by an in e ible linea ope a o on he column space; a change o monomial
basis mul iplies Mk,ℓ(p)on he le / igh by block-diagonal in e ible ma ices. In ei he
case, ma ix ank is in a ian .
In pa icula , Π+ac s block-locally by an in e ible linea map on he column space (and
dually on ows), so le / igh mul iplica ion by he co esponding block-diagonal change-o -
basis ma ices p ese es ma ix ank; hence Γk,ℓ is in a ian unde Π+.
Lemma 19 (Basis in a iance).Changing he monomial o de o coo dina e basis mul iplies
Mk,ℓ(p)on he le / igh by in e ible ma ices; hence Γk,ℓ(p)is basis–in a ian .
P oo . Immedia e om ank(UPS) = ank(P) o any in e ible U, S.
Lemma 20 (Mono onici y Sui e).The SPDP ank Γk,ℓ(p)sa is ies he ollowing p ope ies:
(a) Res ic ion mono onici y (Lemma 16): Fo any es ic ion ρ,Γk,ℓ(p↾ρ)≤Γk,ℓ(p).
(b) P ojec ion mono onici y (Lemma 17): Selec ing a subse o ows o columns canno
inc ease ank.
(c) A ine in a iance (Lemma 18): Fo any in e ible a ine map Φ,Γk,ℓ(p◦Φ) = Γk,ℓ(p).
(d) Basis in a iance (Lemma 19): Changing monomial o de o coo dina e basis p e-
se es Γk,ℓ(p).
P oo . Follows immedia ely om Lemmas 16, 17, 18, and 19.
24
Con en ions. Unless s a ed o he wise, pis he mul ilinea ex ension o a Boolean unc ion;
all anks a e o e he base ield F. When we say “SPDP ank” wi hou pa ame e s, he
ele an (k, ℓ)a e ixed in he su ounding s a emen .
In a iance unde Π+and block-local basis. Each allowed Π+o block-local basis
change ac s in e ibly on he column space by le / igh mul iplica ion o Mk,ℓ(p)by block-
diagonal in e ible ma ices (o e F), hence p ese es ank exac ly. Rank mono onici y
unde es ic ion and p ojec ion ollows om unc o iali y o subs i u ion and subma ix
ank, espec i ely.
De e minis ic compile model (canonical). The compila ion om a uni o m DTM o
a local SoS polynomial is ixed and inpu -independen : adius-1 empla es, laye ed-wi es
and ime× ape iles, cons an an-in, diagonal local basis, and ixed Π+=A. Tag wi es
(phase_id,laye _id,clause_id,wi e_ ole) a e compile -w i en cons an s. This yields
pe -access CEW =O(log log N)and global CEW ≤C(log n)cac oss poly(n)accesses.
Symbol Meaning
ninpu size
Nnumbe o compiled a iables (a e ins umen a ion), N= Θ(n)
Bblock pa i ion o a iables; each block has adius = 1
CEW(p)con ex ual en anglemen wid h o compiled polynomial p
MB
k,ℓ(p)SPDP ma ix, ows (τ, u), cols xβ, en ies coe xβ(u·∂τp)
ΓB
k,ℓ(p) ank o e Fo MB
k,ℓ(p)
PM,n P-side compiled polynomial om DTM M
QΦnNP-side clause-shee SoS o ins ance Φn
TΦblock-local ex ac ion map (basis, a ine, es ic ion, p ojec ion)
Table 2: No a ion used in he SPDP/CEW amewo k.
2.4 Classical B idge: Equi alence o S anda d Complexi y Theo y
A c ucial aspec o ou app oach is es ablishing o mal equi alence be ween he obse e -
heo e ic de ini ions in oduced abo e and s anda d complexi y heo y.
Theo em 21 (Classical–Obse e Equi alence).The ollowing equi alences hold:
1. Pclassical =Pobse e whe e Pobse e ={L:∃Owi h CEW(O)≤ncdeciding L}
2. NPclassical =NPobse e whe e NPobse e ={L:∃Vwi h CEW(V)≤nc e i ying L}
3. The epis emic complexi y class Epis emicP ={L:∃Oobse e wi h bounded esolu ion deciding L}
equals P
25
P
Polynomial
Γk,ℓ ≤nO(1)
Theo em 64
NP
Exponen ial
Γk,ℓ ≥2Ω(n)
Theo em 66
Exponen ial Gap
No poly- ime
algo i hm can
b idge his gap
SPDP Rank Gap: P s. NP
The “God Mo e” (Sec ion 20) ex-
ac s his sepa a ion de e minis ically:
ank-mono one educ ion + iden i y-mino
lowe bound ⇒P=NP (Theo em 143)
Figu e 5: Rank gap a ma ching pa ame e s (NP lowe bound). QΦnexhibi s an
iden i y-mino o size nΘ(log n)a (k, ℓ) = Θ(log n); his con adic s he P-side uppe bound
unde he ank-mono one ex ac ion TΦ.
De e minis ic laye ed b anching p og ams A de e minis ic laye ed b anching p o-
g am (BP) o e a iables x1, . . . , xnis a di ec ed acyclic g aph wi h laye s 0,1, . . . , L, a
single sou ce in laye 0, sinks in laye L, and wid h W= maxτ|Vτ|whe e Vτis he node se
o laye τ. Each edge om laye τ o τ+ 1 is labeled by a li e al λe(x)∈ {1, xi,1−xi}.
Seman ics. Edges ou o a node wi hin a laye ha e disjoin li e al labels whose e alu-
a ions pa i ion {0,1}; hus o any inpu x∈ {0,1}nexac ly one ou going edge is aken a
each isi ed node, yielding a unique laye -by-laye pa h. The leng h is L.
Lemma 23 (Compila ion Lemma (BP simula ion o poly ime)).I L∈Pis decidable in
ime nk, hen o each n he e exis s a de e minis ic laye ed BP Bno leng h L′=nO(k)and
wid h W=nO(1) compu ing χL↾{0,1}n.
Jus i ica ion. Un old he con igu a ion g aph o he ime-nkTM o nks eps; each
32

laye has a mos poly(n)con igu a ions and he ansi ion is de e minis ic gi en he scanned
symbol. Hence L′= Θ(nk),W= poly(n). (Any s anda d TM→BP simula ion su ices.)
We embed χLas a mul ilinea polynomial L:{0,1}n→ {0,1}(and iden i y i wi h i s
unique mul ilinea ex ension o e F).
SPDP ank bound o bounded-wid h/leng h BPs Fo mul ilinea , le Mℓ( )be
he ℓ-shi ed pa ial-de i a i e ma ix: i s ows a e indexed by pai s (S, α)wi h |S|=ℓand
deg(α)≤ℓ; he (S, α)- ow is he coe icien ec o o α·∂ℓ /∂xSin he monomial basis.
W i e kSPDP,ℓ( ) = k Mℓ( ).
We now p o e he key lemma comple ely.
Lemma 24 (BP→SPDP, ixed o de — ull p oo ).S a emen . Le Bbe a de e minis ic
laye ed BP o leng h L′and wid h Wo e {0,1}n, and le be he mul ilinea polynomial i
compu es. Fo any ixed ℓ∈ {2,3},
kSPDP,ℓ( )≤(CℓW L′)dℓ,
o absolu e cons an s Cℓ, dℓdepending only on ℓ. (Fo conc e eness one may ake dℓ=
2ℓ+ 2.)
P oo . We use a ma ix p oduc ep esen a ion and a cylinde decomposi ion.
(1) Ma ix p oduc o m. Index each laye τ= 0, . . . , L′by a s a e se Vτwi h
|Vτ| ≤ W. Le s∈V0be he unique sou ce and le A⊆VL′be he accep ing sinks. Fo
τ= 0, . . . , L′−1de ine he W×Wma ix Mτ(x)whose (u, )en y is he li e al labeling he
edge u→ (i p esen ) and 0o he wise. De e minism pe laye ensu es: o ixed u∈Vτ, he
nonze o en ies in ow uo Mτa e disjoin li e als in {1, xi,1−xi}(so hei sum e alua es
o 1 on any inpu ). Le eube he s anda d basis ec o o s a e u, and a=P ∈Ae . Then
(x) = e⊤
sL′−1
Y
τ=0
Mτ(x)a.
All Mτa e a ine-linea in a single a iable (o cons an ): each laye “que ies” a mos one
inpu a iable due o he pa i ion p ope y.
(2) Di e en ia ion localizes o laye s. Fix an ℓ-se S={i1, . . . , iℓ}and a shi
monomial αwi h deg α≤ℓ. By Leibniz,
α·∂ℓ
xS =X
T⊆{0,...,L′−1},|T|= ≤ℓX
ϕ:T→Sbij.
e⊤
sL′−1
Y
τ=0
B(T,ϕ)
τ(x)a,
whe e o τ /∈T,B(T,ϕ)
τ=Mτ; and o τ∈Twe eplace Mτby i s (nonze o) pa ial
de i a i e w. . . he unique a iable xϕ(τ)used in ha laye , mul iplied by he app op ia e
ac o coming om αi αuses xϕ(τ)a laye τ. Because Mτis a ine-linea in i s (single) laye
a iable, ∂Mτ/∂xiis a cons an ma ix wi h en ies in {0,±1}. The mul iplica i e shi α
can be dis ibu ed so ha all i s ac o s ha li e in laye s o Ta e olded in o a cons an -size
linea combina ion o he same wo li e als {1, xi}(o {1,1−xi}) in hose laye s; ac o s om
33
o he laye s a e abso bed in o neighbo ing cons an ma ices (s ill cons an ank-1 upda es).
Thus, o ixed (S, α), each summand is o he o m
e⊤
sL′−1
Y
τ=0
Mτa,
whe e
Mτ∈Uτand each laye -local space Uτis a ixed-dimension linea space gene a ed by
{Mτ, I, ∂Mτ,and a mos wo li e al-mul iples o Mτ}.
Hence dim Uτ≤C o an absolu e cons an Cindependen o n, W, L′(i depends only on
he ixed se {1, xi,1−xi, ∂xi, ∂(1 −xi)}).
(3) Cylinde decomposi ion by a mos ℓ ouched laye s. Each summand ouches
exac ly he laye s in T(wi h |T|= ≤ℓ) whe e a de i a i e was aken; all o he laye s
con ibu e Mτ∈Uτ(no de i a i e). Fo a ixed o de ed - uple 0≤ 1<··· < ≤L′−1
( he laye s in T), and o any choice o “cu ” s a es
u0∈V0, u1∈V 1+1, . . . , u ∈V +1, u +1 ∈VL′,
inse esolu ions o iden i y P ∈V j+1 e e⊤
=Ibe ween blocks o ac o he p oduc as
e⊤
s 1
Y
τ=0 c
Mτeu1
| {z }
p e ix P0(u1)
· 2
Y
τ= 1+1 c
Mτ
| {z }
middle block
···L′−1
Y
τ= +1 c
Mτa
| {z }
su ix S (u )
whe e each c
Mτ∈Uτand in he ouched laye s we choose c
M j∈ {∂M j,li e al-modi ica ions o M j}.
A e his bookkeeping, e e y summand is a scala ob ained by chaining + 1 block maps
be ween cu s: X
u1,...,u
P0(u1)
|{z}
∈F
·L1(u1, u2)
| {z }
∈F
···L (u , u +1)
| {z }
∈F
·S (u )
|{z}
∈F
.
C ucially, o ixed choices o he ouched laye s and he local pa e n (which de i a i e/li e al
op ion was used in each ouched laye ), each block Lj(·,·)is a bilinea o m whose coe icien
ma ix has size ≤W×Wand belongs o a linea space o cons an dimension (because U j
has cons an dimension and we mul iply a cons an numbe o such ma ices). Thus he
whole amily o such scala s lies in he linea span o he cylinde basis
B:= {P0(·)·L1(·,·)···L (·,·)·S (·) : 0 ≤ ≤ℓ, 0≤ 1<··· < < L′,local pa e ns },
indexed by:
• he choice o ≤ℓ ouched laye s (≤P ≤ℓL′
≤(eL′/ℓ)ℓ),
• he cu s a e uple (u0=s, u1, . . . , u , u +1 ∈A)(≤W +1 ≤Wℓ+1),
•and a local de i a i e pa e n pe ouched laye ; because each laye con ibu es om
he cons an se {1, xi,1−xi, ∂xi, ∂(1 −xi)}, he numbe o dis inc pa e ns is a
cons an cℓdepending only on ℓ.
34
The e o e, o ixed (S, α), e e y ow polynomial α·∂ℓ
xS lies in span(B). Mo eo e , he
same cylinde basis Bwo ks uni o mly o all (S, α)wi h |S|=ℓ,deg α≤ℓ, because (S, α)
only de e mines which c
M jwe pick inside he cons an -size local menu.
(4) Row-space bound. Le c(g)deno e he coe icien ec o o a polynomial gw. . .
he monomial basis. The map g7→ c(g)is linea , hence
{c(α·∂ℓ
xS ) : |S|=ℓ, deg α≤ℓ} ⊆ span {c(b) : b∈B}.
I ollows ha
dim( owspace o Mℓ( )) ≤#B≤cℓ
ℓ·Wℓ+1 ·X
≤ℓL′
≤(CℓW L′)ℓ+1
o a cons an Cℓdepending only on ℓ. (He e we use P ≤ℓL′
≤(eL′/ℓ)ℓ.)
(5) Rank bound. Since he ank o Mℓ( )is a mos i s ow-space dimension, we ob ain
kSPDP,ℓ( )≤(CℓW L′)dℓ
wi h dℓ:= ℓ+ 1. To abso b cons an - ac o o e heads om p e ix/su ix linea iza ions one
may in la e o dℓ= 2ℓ+ 2 wi hou changing polynomial dependence. This comple es he
p oo .
Theo em 25 (P-languages admi polynomial SPDP ank).S a emen . Le L∈Pbe
decidable in ime (n) = nk. Fo each ixed ℓ∈ {2,3}, he e exis s c=c(k, ℓ)such ha
kSPDP,ℓ(χL)≤nc.
Equi alen ly, kSPDP(χL) = nO(k) o ixed ℓ.
P oo . By he Compila ion Lemma, χLa leng h nis compu ed by a laye ed BP wi h
L′=nO(k)and W=nO(1). Apply Lemma 24:
kSPDP,ℓ(χL)≤(CℓWL′)dℓ=nO(k).
Co olla y 26 (P⊆Low SPDP Rank).Fo e e y L∈P he e exis s csuch ha , o all n,
kSPDP(Ln)≤nc,
whe e Lnis L es ic ed o inpu s o leng h n.
P oo . Apply Theo em 25 o a ixed ℓ∈ {2,3}and ake he maximum o e ℓ.
Rema k 5 (Mul ilinea iza ion and Boolean ag eemen ).I he compiled polynomial uses non-
mul ilinea e ms, eplace x
iby xi o ≥1 o ob ain he mul ilinea iza ion ml. Then ml =
χLon {0,1}n. The SPDP cons uc ion eads coe icien s o shi ed de i a i es; es ic ing
o {0,1}nand o he pa h-polynomial span can only educe he ma ix, so kSPDP,ℓ( ml)≤
kSPDP,ℓ( ).
35
3.2 Low- ank ⇒P (De e minis ic In e pola ion Algo i hm) [Op-
ional]
This sec ion is no used in he sepa a ion p oo . I shows ha low SPDP ank yields a
de e minis ic spa se-basis ep esen a ion and hence a polynomial- ime decision p ocedu e.
Th oughou , ix a cons an de i a i e o de c∈ {2,3}.
Theo em 27 (Spa se-basis eco e y in poly ime — Op ional).Le (x1, . . . , xn)be a deg ee-
dpolynomial o e a ield Fwi h
kSPDP,c( )≤n6.
The e is a de e minis ic algo i hm unning in nO(c) ime ha ou pu s
1. a monomial basis Bo size |B| ≤ n6, and
2. he coe icien ec o o in ha basis.
Consequen ly, he decision p oblem compu ed by can be sol ed in ime O(n6)by e alua ing
he eco e ed spa se o m.
Se up and p imi i es Field/deg ee. Wo k o e cha ac e is ic 0(o any p ime p >
poly(n)) so all linea algeb a and ini e-di e ence iden i ies a e alid. Use he s anda d
K onecke subs i u ion wi h base B= poly(n)when needed so all induced uni a ia e deg ees
a e poly(n).
Rows ia ini e di e ences (o de c). Fo any poin x∈ {0,1}nand any |S| ≤ c, he
mixed pa ial ∂|S| /∂xSa xcan be compu ed by a linea combina ion o a mos 2|S|≤2c
e alua ions o a Hamming neighbo s o x. Thus each alue o α·∂≤c ( o deg α≤c)
cos s O(2c)black-box e alua ions o .
TM simula ion o acle. Each e alua ion (y)can be compu ed by simula ing he
deciding TM in ime nk. Hence each ow e alua ion abo e cos s O(2cnk).
Columns as monomial unc ionals. Fo a monomial m(x), he alue α·∂≤cma any
xis explici : i is ei he 0o a {±1}-mul iple o a (lowe -deg ee) monomial e alua ed a x.
The e o e we can compu e column en ies o monomials wi hou que ying .
Hi ing se o de e minism. Use you explici hi ing se H(seed leng h O(log n); see
§17.7.4) o choose e alua ion con igu a ions ha gua an ee ull- ank mino s o any column
sub amily o size ≤n6. Conc e ely, we selec T= Θ(n6) ow unc ionals
Ej(·) = αj(x)·∂|Sj|(·)/∂xSje alua ed a x(j)∈H,
wi h |Sj| ≤ cand deg αj≤c, so ha he T× ma ix [Ej(m)]j,m∈Bis nonsingula o e e y
monomial se Bo size ≤n6.
Algo i hm 12′(De e minis ic SPDP-Basis Reco e y) Inpu : o acle o ia TM
simula ion; pa ame e s n, k, c; deg ee bound d.
Ou pu : a monomial basis Bwi h |B| ≤ n6and coe icien s {ˆ
m:m∈B}such ha
=Pm∈Bˆ
mm.
36
1. Build he measu emen ec o ( ows om ).
Choose T= Θ(n6)con igu a ions {(x(j), Sj, αj)}T
j=1 as abo e om he hi ing-se sched-
ule. Fo each j, compu e
bj:= Ej( ) = αj(x)·∂|Sj| /∂xSjx=x(j)
using a mos 2ce alua ions o a nea by poin s ( ini e di e ences). Cos : T·
O(2cnk) = O(nk+6).
2. De e minis ic ank- e ealing column selec ion (no enume a ion).
We access columns implici ly: gi en a monomial m, we can compu e he column ec o
(m) := (E1(m), . . . , ET(m)) ∈FT
in poly(n) ime (each en y is a i ial symbolic de i a i e o me alua ed a x(j)).
Run a de e minis ic ank- e ealing p ocedu e (e.g., g eedy Gaussian elimina ion wi h
exac a i hme ic, o RRQR o e he implici column o acle) ha i e a i ely adds m’s
whose (m)inc eases he span on FTun il he span con ains b= (b1, . . . , bT).
By he low- ank p emise, he column space o Mc( )has dimension ≤n6. Ou hi ing-
se choice ensu es ha some se o ≤n6monomial columns is independen unde {Ej}.
The p ocedu e e u ns such a se B={m1, . . . , m }, ≤n6, and coe icien s γ∈F
wi h
b=
X
i=1
γi (mi).
3. Reco e he ac ual coe icien s o on B.
Pick any esh poin s y(1), . . . , y( )∈H. Fo m he linea sys em
(y(ℓ)) =
X
i=1
ˆ
mimi(y(ℓ)) (ℓ= 1, . . . , ),
using TM simula ion o ob ain he le -hand side. The × ma ix [mi(y(ℓ))] is a
Vande monde- ype/e alua ion ma ix ha is nonsingula by he hi ing-se gua an ee.
Sol e o ˆ
mi.
Complexi y.
•E alua ions: O( ) = O(n6)poin s, each in ime nk⇒O(nk+6).
•Linea algeb a: sol e an × sys em in O( ω) = O(n6ω) ime (conse a i ely, O(n18)).
•Column-o acle a i hme ic is poly(n)pe pi o and domina ed by he e ms abo e.
O e all un ime: nO(c)(wi h c ixed and all exponen s polynomial in k).
37

Co ec ness Low ank ⇒small column dimension. kSPDP,c( )≤n6means he col-
umn space o he ℓ-shi ed pa ial-de i a i e ma ix ( o ℓ=c) has dimension ≤n6. Columns
a e indexed by monomials (up o he ele an deg ee). Hence he e exis s a monomial se B
o size ≤n6whose columns o m a basis o ha space.
Hi ing-se soundness. The chosen measu emen unc ionals {Ej}(shi ed-de i a i e
e alua ions a Hpoin s) induce a linea map ha is injec i e on e e y ≤n6–dimensional
column subspace; equi alen ly, o any such B, he ma ix [Ej(m)]j,m∈Bis nonsingula .
Rank- e ealing selec ion inds B.Since b= (Ej( ))jis a linea combina ion o mono-
mial columns wi hin ha space, he de e minis ic ank- e ealing ou ine selec s a spanning
se Bo size ≤n6and exp esses bin ha basis.
Coe icien eco e y is unique. The e alua ion ma ix [mi(y(ℓ))] o e His ull ank
o |B|poin s, so he coe icien s {ˆ
mi}a e uniquely de e mined.
Decision p ocedu e. The eco e ed ep esen a ion (x) = Pm∈Bˆ
mm(x)e alua es
in O(|B|) = O(n6) ime on any inpu x. Thus he unde lying language is decidable in
polynomial ime.
Rema k 6 (Wha we did no assume).We did no assume Fou ie spa si y o use he
Mansou –Shi lea ne . We only used: (i) he low SPDP- ank hypo hesis; (ii) explici hi ing
se s ( om §17.7.4); (iii) TM simula ion o e alua ions; and (i ) s anda d ini e-di e ence
iden i ies and de e minis ic linea algeb a.
3.3 B idge Be ween Pa ial-De i a i e and SPDP Rank
3.3.1 Comple e B idge P oo
We compa e he classical pa ial-de i a i e coe icien ma ix agains he global SPDP ma-
ix (i.e., SPDP ows aken o e all de i a i e o de s ℓ≥0, wi h shi α anging o e all
monomials; his sec ion does no es ic ℓ o {2,3}).
De ini ion (Pa ial-de i a i e coe icien ma ix). Fix a pa i ion [n] = S⊔T. Fo a
mul ilinea polynomial p∈F[x1, . . . , xn], le
MS={xU:U⊆S}, MT={xV:V⊆T}
be he monomial amilies o e Sand T. The ma ix
PDS,T (p)∈FMT×MS
has ows indexed by xV∈MTand columns by xU∈MS, wi h en y
PDS,T (p)V,U := [xVxU]p,
he coe icien o he monomial xVxUin p.
38
De ini ion (Global SPDP ma ix). Le MSPDP(p)be he ( ow-conca ena ed) ma ix
whose ows a e he coe icien ec o s o α·∂|R|
xRpin he ull monomial basis o e [n], anging
o e all pai s (R, α)wi h R⊆[n]and αany monomial (no deg ee cap needed o mul ilinea
p). I s ank is he global SPDP ank, kall
SPDP(p).
(You main heo ems only use ixed o de s ℓ∈ {2,3}; he e we allow all o de s pu ely o
his compa ison lemma.)
Lemma 28 (Pa ial de i a i es o m a subma ix).Fo mul ilinea pand any pa i ion
[n] = S⊔T,
ank PDS,T (p)≤ ank MSPDP(p)= kall
SPDP(p).
P oo . Fix S, T as abo e. Fo each U⊆S, conside he SPDP ow co esponding o (R=
U, α = 1); his ow is he coe icien ec o o ∂|U|
xUp. Because pis mul ilinea ,
∂|U|
xUp=X
V⊆T[xVxU]pxV,
i.e., i s suppo lies en i ely in monomials o e T, and he coe icien o xVequals he coe -
icien o xVxUin p.
Now es ic he columns o he global SPDP ma ix o he monomials o e T(i.e., keep
only columns indexed by xVwi h V⊆T), and es ic he ows o he subse {(R=U, α =
1) : U⊆S}. On his block, he en y a ow U, column Vis p ecisely [xV]∂|U|
xUp= [xVxU]p.
The e o e his block is exac ly PDS,T (p)⊤( he anspose o PDS,T (p)).
Hence PDS,T (p)(up o ansposi ion) is a li e al subma ix o MSPDP(p). Subma ix ank
ne e exceeds he ambien ank, so
ank PDS,T (p)≤ ank MSPDP(p).
Rema k 7 (Why we didn’ use e alua ions).An “e alua ion ma ix” E[a, b] = p(a)would
be ank-1 and un ela ed o SPDP. The b idge is pu ely coe icien -le el: SPDP ows a e
coe icien ec o s o shi ed pa ials; choosing α= 1 and a ying R⊆S, hen p ojec ing o
columns o e T, eco e s he classical ∂-ma ix.
3.4 Ba ie T anscendence A gumen s
This sec ion shows ha ou me hod does no ela i ize (§2.4.1) and is no a na u al p oo in
he algeb aic sense (§2.4.2). These esul s a e used la e in §9 (Ba ie Immuni y Summa y).
3.4.1 Rela i iza ion Ba ie — Comple e P oo
Theo em 29 (Non- ela i izing me hod).The e exis s an o acle Asuch ha PA=NPA[17],
while ou SPDP lowe bounds emain alid ela i e o A. Consequen ly, he p oo echnique
o §2 (which combines he uppe bound P⊆LowSPDP wi h explici SPDP lowe bounds)
does no ela i ize.
39
P oo . Take A= QBF (PSPACE-comple e). I is s anda d ha
PA=NPA= PSPACE.
Hence no ela i izing p oo can sepa a e PA om NPA.
Now obse e wo ac s abou ou echnique:
Algeb aic lowe bounds pe sis . Any algeb aic lowe bound o he SPDP ank o
a ixed polynomial (e.g., Pe mn) is a s a emen in e nal o coe icien s/de i a i es and is
independen o an o acle on a Tu ing machine. Thus, o e e y o acle A,
kA
SPDP,ℓ(Pe mn) = kSPDP,ℓ(Pe mn)≥2Ω(n)( o ixed ℓ),
by he same algeb aic a gumen as in he un ela i ized wo ld. In pa icula , he exponen ial
lowe bound
kSPDP,ℓ(Pe mn)≥2Ω(n)
a ises om he Lag angian analysis de eloped in §14.2, whe e he non-degene acy o he
Lag angian po en ial L(Φ) ensu es exponen ial independence among shi ed pa ial de i a-
i es. We e e ence his o mal de i a ion la e when comple ing he lowe -bound hal o he
sepa a ion.
The uppe bound P⊆LowSPDP need no ela i ize. Ou uppe bound p oceeds ia
b anching p og ams wi hou o acle ga es (§2.1). A PA-machine can make o acle que ies ha
canno , in gene al, be simula ed wi hin he BP→SPDP pipeline unde he same pa ame e s.
The e o e we canno conclude PA⊆LowSPDP.
Pu ing hese oge he : o A= QBF we ha e PA=NPAwhile he SPDP lowe bounds
con inue o hold. Hence ou p oo echnique is non- ela i izing.
Rema k 8.One may eplace Pe mnwi h any explici polynomial o which he pape p o es
an ℓ-SPDP ank lowe bound o 2Ω(n); he s a emen emains he same.
3.4.2 Na u al P oo s Ba ie — Algeb aic Non-Na u ali y (Comple e)
The Razbo o –Rudich “na u al p oo s” amewo k [21] demands (i) la geness ( he p ope y
holds o a 2−O(n) ac ion o Boolean unc ions) and (ii) cons uc i i y (decidable in poly(n)
gi en a u h able). We show ha he low-SPDP- ank p ope y used by ou uppe bounds
ails bo h equi emen s in an algeb aic sense. This su ices o explain why ou me hod e ades
he Na u al P oo s ba ie .
Fix a de i a i e o de ℓ∈ {2,3}and a polynomial bound (n) = nO(1). De ine
Plow(n) := { : kSPDP,ℓ( )≤ (n)}.
Theo em 30 (Algeb aic non-na u ali y o low SPDP ank).Fo each n,Plow(n)is (i) no
la ge in he algeb aic sense (Za iski-meag e / measu e-ze o in coe icien space), and (ii) no
cons uc i e om u h ables in poly(n) ime. Hence he SPDP- ank p ope y used by ou
amewo k is no “na u al”.
40
P oo . (i) No la ge (algeb aic). Fix a deg ee bound d(as in ou Boolean→polynomial
embedding). View as a poin in he coe icien space FN, whe e
N=
d
X
i=0 n
i=n
≤d.
Fo each , he ℓ-SPDP ma ix Mℓ( )has en ies ha a e polynomial unc ions o he
coe icien s o . The condi ion k Mℓ( )≤ holds i all ( + 1) ×( + 1) mino s o Mℓ( )
anish—i.e., lies in he common ze o se o a ini e amily o polynomials in FN. The e o e
V ,ℓ := { : kSPDP,ℓ( )≤ }
is a p ope algeb aic a ie y (s ic ly lowe dimension han N) whene e he gene ic ank
exceeds (which holds o all polynomial (n)in ou deg ee egime). Hence V ,ℓ has Lebesgue
measu e ze o o e R, and negligible measu e o e any su icien ly la ge ini e ield. In pa -
icula , he p ope y is no la ge in he algeb aic sense.
(ii) No cons uc i e ( u h- able inpu ). Suppose we a e gi en he ull u h able
o :{0,1}n→ {0,1}(size 2n). To decide whe he kSPDP,ℓ( )≤ , one mus , in gene al,
compu e (o ce i y) he ank o Mℓ( ). E en o ming he ele an po ion o Mℓ( ) equi es
enume a ing monomials up o deg ee d= Θ(n), whose coun is
N=
d
X
i=0 n
i= 2Θ(n).
Any exac algo i hm mus pe o m a leas Ω(N)a i hme ic ope a ions jus o ead he
induced da a, and ank compu a ion akes Ω(N2) ield ope a ions in he wo s case. Since
N= 2Θ(n), his is supe polynomial in n. The e o e he p ope y is no decidable in poly(n)
ime om he u h able (i.e., i is no cons uc i e in he Razbo o –Rudich sense).
Rema ks.
•We in en ionally a oid claiming #P-ha dness; he uncondi ional size-o -ma ix a gu-
men al eady su ices o iola e cons uc i i y.
•I one es ic s o andom polynomials wi h ull-dimensional coe icien dis ibu ions,
pa (i) s eng hens o “p obabili y 0” o low ank; we do no need a ine Boolean
densi y bound he e.
Conclusion o §2.4.1–2.4.2. The algeb aic lowe bounds we use pe sis unde o acles,
while he uppe bound P⊆LowSPDP does no ela i ize, so he echnique is non- ela i izing.
Mo eo e , he low- ank p ope y is algeb aically meag e and no cons uc i e om u h a-
bles, so he me hod e ades na u al p oo s in he ele an sense.
41
o ank . Equi alen ly, he column space o Mis a -dimensional subspace o FR
q, and M
maps he s anda d basis o FC
qin o his subspace ia a su jec i e linea map.
To coun , we:
(i) Choose a -dimensional column space V⊆FR
q: he e a e a mos qR choices (each
subspace is de e mined by a ull- ank R× ma ix).
(ii) Choose a su jec i e linea map FC
q→V: any such map is de e mined by he images o
he Cs anda d basis ec o s, each lying in he -dimensional space V, gi ing a mos
qC choices.
Mul iplying yields qR ·qC =q (R+C). Howe e , his o e coun s by he au omo phism g oup
o he pai (V, basis o V), which is GL (Fq)o size oughly q 2. Hence he numbe o ank-
ma ices is a mos q (R+C)/q 2=q (R+C− ).
Summing o e = 0, . . . , gi es he s a ed bound
#{R×Cma ices o ank ≤ } ≤
X
=0
q (R+C− ).
This comple es he jus i ica ion.
Se =nc. Since R= Θ(nO(ℓ))and C= 2n, we ha e
P
 k(Mℓ( )) ≤nc≤q−Ω(R C)=q−Ω(nO(ℓ)·2n)≤2−Ω(2n).
The e o e |Fn,c|/22n≤2−Ω(2n), as claimed.
Consequences o Na u al P oo s.
1. La geness ails. The densi y 2−Ω(2n)is a below he Razbo o –Rudich h eshold
1/poly(2n).
2. Cons uc i i y is moo . Since he p ope y is anishingly small, he na u al-p oo s
ba ie does no apply e en i membe ship we e decidable in 2O(n) ime.
Hence, he p ope y “ kSPDP,ℓ( )≤nc” is non-na u al uncondi ionally.
Theo em 35 (E alua ion om a low- ank ce i ica e).Le :{0,1}n→ {0,1}be a Boolean
unc ion and ix an o de ℓ≥0. Suppose we a e gi en a low- ank ce i ica e o consis ing
o :
1. a ank ac o iza ion o he o de -ℓSPDP ma ix,
Mℓ( ) = U V, U ∈FR× , V ∈F ×C, = kSPDP,ℓ( ),
whe e R= Θ(nO(ℓ))and C= 2n;
2. and an implici column applica ion ou ine ha , on inpu x∈ {0,1}n, compu es V χ(x)
in poly(n, ) ime, whe e χ(x)∈FCis he monomial-e alua ion ec o χ(x)m=m(x).
48

Then (x)can be e alua ed in ime poly(n, ).
Rema ks on he assump ion. (i) Fo he global SPDP ma ix (conca ena ing all
de i a i e o de s, including ℓ= 0), he ℓ= 0 block is he coe icien ec o o ; in ha case
he ex ac o below is i ial. (ii) Fo he compiled classes we wo k wi h (§2.1, PAC/ABP
ou es), he ma ix ac o iza ions U, V inhe i s uc u e ha suppo s as column applica ion
x7→ V χ(x)(e.g., ia p oduc -o -small ac o s), so he assump ion holds in ou use-cases.
P oo . W i e c∈FC o he coe icien ec o o in he mul ilinea monomial basis. Then
o any inpu x,
(x) = ⟨χ(x), c⟩=χ(x)⊤c.
Because Mℓ( ) = UV has ank , he ow-space and column-space coincide wi h he
images o Uand V⊤, espec i ely. The e exis s a (p ecompu able) linea ex ac o E∈FC×R
o size poly(n)such ha
c=E Mℓ( )⊤y=E V ⊤U⊤y
o some y∈FR(in ui i ely: Epicks a ixed linea combina ion o o de -ℓshi ed-de i a i e
ows ha in e s he di e en ial ope a o back o coe icien s; when he global SPDP is
used, one can ake E o be he i ial selec o o he ℓ= 0 block). P ecompu e a le -in e se
L∈F ×R o Uon he image o U(e.g., ia ank- e ealing QR/Ba eiss on U), so LU ac s
as he iden i y on im(U).
Then
(x) = χ(x)⊤c=χ(x)⊤E V ⊤U⊤y= (V χ(x))⊤(E⊤y′),whe e y′:= U⊤y∈im(U⊤).
The ec o z(x) := V χ(x)∈F can be compu ed in poly(n, ) ime by hypo hesis
(implici column applica ion). The mul iplie w:= E⊤y′∈F is independen o xand is
p ecompu able in poly(n, ) ime om he ce i ica e by sol ing a small linea sys em ha
pins c(o , in he global SPDP case, by di ec ly selec ing he ℓ= 0 block). The e o e,
(x) = ⟨z(x), w⟩,
and e alua ing (x) akes O( ) ield ope a ions once z(x)is a ailable. O e all cos is
poly(n, ).
No ci cula i y a ises: we ne e que y as an o acle; we only use he low- ank ac o iza ion
and he ixed ex ac o Ep o ided by (o p ecompu able om) he ce i ica e s uc u e o
he compiled class.
Summa y. Lemma 34 shows ha low SPDP ank is an exponen ially a e p ope y among
Boolean unc ions, uncondi ionally uling ou “la geness” in he sense o Na u al P oo s.
Theo em 35 explains ha , o he compiled classes we manipula e, a low- ank ce i ica e
gi es polynomial- ime e alua ion, aligning wi h ou P-side uni o m collapse and keeping he
amewo k non-ci cula .
49
3.9 Pu ing I All Toge he
Wi h Theo em 35, he de e minis ic ke nel- ec o cons uc ion, and he uncondi ional non-
na u ali y esul , all logical dependencies in he p oo o P=NP a e now closed. The
amewo k in eg a es he uppe and lowe bounds, he wi ness cons uc ion, and he ba ie
immuni y a gumen s in o a cohe en , non-ci cula whole.
Checklis .
✓Exponen ial SPDP- ank lowe bound o #3SAT →diagonalizable sepa a ion.
✓Polynomial- ime e alua ion om low ank (no ci cula i y).
✓De e minis ic ke nel ec o w∈V⊥
nse ing as a polynomial- ime wi ness.
✓Ba ie a gumen s bypass bo h na u al-p oo s and ela i iza ion.
✓En i e logical chain closed wi hin he algeb aic-analy ic amewo k.
4 No e on Lean Fo maliza ion and Comple ion
The a gumen de eloped so a is en i ely o malizable in Lean 4, equi ing only he s anda d
de ini ions o P,NP, and polynomial- ime e i ie s. Comple ing he Lean p oo in ol es
h ee modules co esponding o he co e esul s o Sec ion 2:
Polynomial uppe bound (P⊆Low SPDP). The o mal s uc u e comp ises: polyno-
mial uppe bound (P-side collapse), exponen ial lowe bound (NP-side ha dness), o hogonal
wi ness cons uc ion (God Mo e), and he main sepa a ion heo em.
5 Obse e Model: CEW-Bounded Compu a ion
5.1 Obse e ame and CEW
We quan i y an obse e ’s ep esen a ional capaci y by he Con ex ual En anglemen Wid h
(CEW)— he la ges numbe o inpu s ha can “join ly in e ac ” in i s mul ilinea ep esen-
a ion.
De ini ion 14 (Mul ilinea ep esen a ion and CEW).Fix a ield Fo cha ac e is ic 0o a
su icien ly la ge p ime. Fo a Boolean unc ion :{0,1}n→ {0,1}, le ˜
∈F[x1, . . . , xn]be
i s unique mul ilinea polynomial ha ag ees wi h on {0,1}n:
˜
(x) = X
S⊆[n]
ˆ
(S)xS, xS:= Y
i∈S
xi.
De ine
CEW( ) := max{|S|:ˆ
(S)= 0 }
(i.e., CEW( ) = deg( ˜
)).
50
De ini ion 15 (Obse e classes).Fo each n, le
PolyObsn:= { :{0,1}n→ {0,1} | CEW( )≤nO(1) },
ExpObsn:= { :{0,1}n→ {0,1} | CEW( )≤2Θ(n)}.
P oposi ion 36 (BP deg ee ⇒polynomial CEW).Le Bbe a de e minis ic laye ed b anch-
ing p og am (BP) o leng h Lo e a iables x1, . . . , xnwi h edge labels in {1, xi,1−xi}, and
le be i s compu ed unc ion. Then
CEW( )≤L.
P oo . Each accep ing pa h con ibu es a pa h polynomial gi en by he p oduc o i s Ledge
labels; hence deg ee ≤L. Mul ilinea iza ion does no inc ease deg ee, and summing pa hs
p ese es he maximal deg ee bound. Thus deg ˜
≤L.
Co olla y 37 (P⊆PolyObs ia BP compila ion).I a language L∈Pis decidable in ime
nk, hen o each n he cha ac e is ic unc ion χLadmi s a ep esen a ion wi h CEW(χL)≤
nO(k). Hence χL∈PolyObsn.
P oo . By he poly ime→BP compila ion (Sec ion 2.1), χLis compu ed by a laye ed BP o
leng h L′=nO(k). Apply P oposi ion 36.
5.2 F om SPDP ank o CEW
We ela e SPDP ank o CEW: bounded CEW limi s he column space o he SPDP ma ix
o any ixed de i a i e o de .
Lemma 38 (Deg ee bounds columns ⇒ ank bound).Le :{0,1}n→ {0,1}ha e mul i-
linea deg ee d= CEW( ). Fix any cons an o de ℓ≥0. Then
kSPDP,ℓ( )≤
d
X
j=0 n
j.
P oo . An o de -ℓ ow o he SPDP ma ix Mℓ( )is he coe icien ec o o α·∂|R| wi h
|R|=ℓand deg α≤ℓ. Di e en ia ion lowe s deg ee by ℓ, he shi by αadds ≤ℓ, so he
esul ing deg ee ≤d. Thus no column indexed by a monomial o deg ee > d can appea wi h
a nonze o coe icien in any ow. The column space lies in he span o monomials o deg ee
≤d, whose numbe is Pd
j=0 n
j. Rank is a mos he column-space dimension.
Lemma 39 (Exponen ial SPDP ank ⇒linea CEW).Fix ℓ≥0. Suppose a amily { n}
sa is ies kSPDP,ℓ( n)≥2γn o some cons an γ > 0. Then
CEW( n)≥c n
o some cons an c=c(γ)>0and all su icien ly la ge n.
51
P oo . Le dn= CEW( n). I dn≤δn o δ∈(0,1), hen by Lemma 38
kSPDP,ℓ( n)≤
⌊δn⌋
X
j=0 n
j≤2H(δ)n,
whe e His he bina y en opy. Choosing δ < H−1(γ)yields 2H(δ)n<2γn o la ge n, a
con adic ion. Hence dn≥cn wi h c:= H−1(γ)>0.
Co olla y 40 (Classical ∂-LB ⇒la ge CEW).I {pn}has ank(PDSn,Tn(pn)) = 2Ω(n) o
some |Sn| ≤ ℓ, hen CEW(pn)≥Ω(n).
P oo . By he uni o m-mono onici y b idge (Sec ions 2.6–2.7), kSPDP,ℓ(pn)≥2Ω(n). Apply
Lemma 39.
Co olla y 41 (En opy- igh CEW s. SPDP ank).Fo any ℓ≥0and any :{0,1}n→
{0,1},
minnd:
d
X
j=0 n
j≥ kSPDP,ℓ( )o≤CEW( )≤n.
In pa icula , i kSPDP,ℓ( )≥2γn hen CEW( )≥(H−1(γ)−o(1)) n; con e sely, i
CEW( )≤δn hen kSPDP,ℓ( )≤2H(δ)n.
P oo . The le inequali y is Lemma 38 in e ed (mono onici y o he cumula i e binomial
sum); uppe bound CEW( )≤nis i ial. The en opy- o m bounds a e he s anda d
es ima es o Pj≤δn n
j.
5.3 Epis emic complexi y classes
We mi o classical P/NP inside he obse e /CEW model.
De ini ion 16 (Epis emic P).Epis emicP(n)is he se o :{0,1}n→ {0,1}wi h
CEW( )≤nO(1).
De ini ion 17 (Epis emic NP).Epis emicNP(n)is he se o :{0,1}n→ {0,1} o which
he e exis s a polynomial pand a polynomial- ime e i ie Vsuch ha
(x) = 1 ⇐⇒ ∃w∈ {0,1}≤p(n)V(x, w) = 1,
and, o each ixed w, he accep ance p edica e x7→ V(x, w)has CEW ≤nO(1).
Rema k 12.Fo s anda d NP p edica es (e.g., CNF-SAT), accep ance is local/low-deg ee,
hence he CEW bound holds au oma ically.
52
5.4 Obse e esou ce sepa a ion and Epis emicP ⊊Epis emicNP
Theo em 42 (Obse e hie a chy).Fo e e y n,PolyObsn⊊ExpObsn.
P oo . Inclusion is immedia e. Fo s ic ness, ake a ha d amily { n}(Lag angian/Tsei in;
c . §6/§14) wi h exponen ial classical ∂-ma ix ank; by Co olla y 40, CEW( n)≥Ω(n), so
n∈ExpObsn PolyObsn.
Theo em 43 (Epis emic P⊊NP).Fo all su icien ly la ge n,
Epis emicP(n)⊊Epis emicNP(n).
P oo . (Inclusion) I ∈P, Co olla y 37 gi es CEW( )≤nO(1), hence ∈Epis emicP(n)⊆
Epis emicNP(n)( ake emp y wi ness).
(S ic ness) Le { n}be he explici NP amily om he Lag angian/Tsei in con-
s uc ion (e.g., 3-SAT on expande empla es). These ha e polynomial- ime e i ie s, so
n∈Epis emicNP(n). By Co olla y 40, CEW( n)≥Ω(n), hus n/∈Epis emicP(n).
Rema k 13 (Obse e dualiza ion).Wi hin he N-F ame obse e -cen ic eading, cons uc -
ing a global dual w∈V⊥
n(Sec ion 2.7) is he “God-mo e”: i algeb aically collapses he
polynomial- ime subspace o i s o hogonal complemen , exposing ( ia CEW and SPDP)
he esou ce bounda y be ween wha polynomial obse e s can compu e and wha hey can
only e i y.
6 The Obse e –Classical B idge: Fo mal Equi alence o
Compu a ional F amewo ks
6.1 Resou ce-Bounded Sepa a ion (Fo mal S a emen )
We summa ize he sepa a ion in pu ely algeb aic/obse e e ms, using esul s es ablished
in §2 (BP→SPDP uppe bounds; uni o m-mono onici y b idge; wi ness cons uc ion) and
§4 (CEW s. SPDP).
Theo em 44 (Resou ce-bounded sepa a ion).Fix any cons an de i a i e o de ℓ∈ {2,3}.
The e exis s an explici amily { n}such ha
1. (Uppe o P)Fo e e y g∈P, kSPDP,ℓ(gn)≤nO(1) and CEW(gn)≤nO(1).
2. (Lowe o he ha d amily) kSPDP,ℓ( n)≥2Ω(n)and he e o e CEW( n)≥Ω(n).
3. (Obse e sepa a ion) Epis emicP(n)⊊Epis emicNP(n)(Theo em 43), wi nessed
by { n}.
P oo (summa y). (1) ollows om §2.1 (poly ime→BP→SPDP) and P oposi ion 36. (2)
ollows om he Lag angian/Tsei in lowe bound (see §6/§14) plus he ∂- o-SPDP b idge
(§2.6–§2.7). (3) is Theo em 43.
53

6.2 SPDP Theo y: Mul ilinea Founda ions (Wha We Ac ually
Use)
We collec only he iden i ies needed o §2–§4 (and used implici ly in §6).
Lemma 45 (Unique mul ilinea iza ion).E e y :{0,1}n→ {0,1}has a unique ˜
∈
F[x1, . . . , xn]mul ilinea wi h ˜
|{0,1}n= .
Lemma 46 (Deg ee = CEW).
deg( ˜
) = CEW( ) = max{|S|:ˆ
(S)= 0 }.
Lemma 47 (Column bound o o de -ℓSPDP; c . §4.2).I CEW( ) = d, hen
kSPDP,ℓ( )≤
d
X
j=0 n
j.
Lemma 48 (Uni o m mono onici y; c . §2.6–§2.7).Fo any pa i ion [n] = S⊔Twi h
|S| ≤ ℓ, he pa ial-de i a i e ma ix PDS,T ( )appea s (up o anspose) as a subma ix o
he o de -ℓSPDP ma ix. Hence
ank(PDS,T ( )) ≤ kSPDP,ℓ( ).
Co olla y 49 (En opy- igh CEW↔SPDP; c . §4.2).I kSPDP,ℓ( )≥2γn hen CEW( )≥
(H−1(γ)−o(1)) n; i CEW( )≤δn hen kSPDP,ℓ( )≤2H(δ)n.
Rema k 14.These a e he p ecise ools you ac ually use la e ; he p e ious “e al monomial”
i ems can be d opped.
6.3 Obse e –Classical B idge (Exac Compila ion)
We o malize he exac ma ch be ween classical compu a ion and he obse e /CEW pic u e.
Theo em 50 (Exac poly ime→obse e compila ion).Le Mbe a polynomial- ime decide
o L. The e exis s a laye ed BP Bno leng h nO(1) and polynomial wid h such ha he
Boolean unc ion n=χLcompu ed by Ma leng h nequals he unc ion compu ed by Bn.
Consequen ly,
CEW( n)≤nO(1), kSPDP,ℓ( n)≤nO(1) (ℓ∈ {2,3}).
P oo . S anda d TM→BP simula ion yields Bnwi h leng h nO(1) and wid h nO(1) (c . §2.1).
P oposi ion 36 gi es he CEW bound; §2.1 gi es he SPDP bound.
Theo em 51 (Explici ha d amily ⇒obse e sepa a ion).Le { n}be he Lag angian/T-
sei in amily (see §6/§14) wi h ank(PDSn,Tn( n)) = 2Ω(n) o some |Sn| ≤ ℓ. Then
CEW( n)≥Ω(n)and kSPDP,ℓ( n)≥2Ω(n).
Hence n/∈PolyObsnbu n∈Epis emicNP(n).
P oo . Uni o m-mono onici y (Lemma 48) ans e s he ∂-LB o SPDP; Lemma 47/Co . 49
lowe -bound CEW. Ve i iabili y is s anda d (NP wi ness), so n∈Epis emicNP(n).
54
6.4 Ma hema ical Soundness: Global Dual and Non-Ci cula i y
We consolida e he wi ness cons uc ion and co ec ness gua an ees.
Theo em 52 (De e minis ic dual w∈V⊥
n; c . §2.7).Le Vnbe he span o he compiled
“P-side” e alua ions ( ows chosen by he ixed iple-shi scheme). The e is a de e minis ic
algo i hm unning in ˜
O(n12)bi ime ha ou pu s a nonze o w∈V⊥
n.
P oo . Assemble he iple-shi momen ma ix Ao size × wi h ≤n3; compu e a
nonze o le -ke nel ec o by Ba eiss; e i y o hogonali y on a ini e hi ing se H= [n]3.
See §2.7 o de ails and bi -size bounds.
Theo em 53 (Comple eness and Soundness o he ce i ica e).Le wbe as abo e. Then:
1. (Comple eness) Fo e e y g∈P(compiled by he ixed pipeline), ⟨w, g(·+h)⟩= 0
o all indexed shi s h∈[n]3.
2. (Soundness) Fo he ha d amily n(Lag angian/Tsei in), ⟨w, n(·+h⋆)⟩ = 0 o
some ixed h⋆∈[n]3.
P oo . Comple eness: w∈V⊥
nby cons uc ion, and Vncon ains all compiled P-side ows
indexed by [n]3. Soundness: he exponen ial SPDP/CEW lowe bounds gua an ee ha he
ha d amily escapes he compiled low- ank span; he ixed index se con ains a wi ness shi
wi h nonze o p ojec ion (as in §2.7).
Co olla y 54 (Non-ci cula e alua ion).Gi en a low- ank ce i ica e o g( ank ac o iza-
ion wi h e icien column applica ion), g(x)can be compu ed in poly(n, kSPDP,ℓ(g)) ime
(Theo em 35). Toge he wi h Theo em 53, he sepa a ion uses only algeb aic ce i ica es and
ixed compila ion—no o acle calls o he a ge unc ion—so he a gumen is non-ci cula .
7 Epis emic Complexi y Classes and he Obse e Hie -
a chy
Building on he obse e –classical b idge (§5), we o malize epis emic complexi y classes—
compu a ional classes de ined by he in e en ial limi s o bounded obse e s—so ha hey
align cleanly wi h classical P/NP while p ese ing he CEW lens de eloped in §§2–4.
Rema k 15 (Pu pose o his sec ion).This sec ion is included only o si ua e he algeb aic and
SPDP- ank a gumen s wi hin he b oade obse e - heo e ic amewo k de eloped elsewhe e.
I is no equi ed o any o mal heo em in his pape , bu i helps cla i y he concep ual
o igin o he CEW and “obse e ” e minology used h oughou . Reade s may iew i as an
in e p e i e b idge connec ing he p esen p oo a chi ec u e o a wide heo y o bounded
obse e s and epis emic compu a ion.
55
7.1 Obse e s and CEW
We e ain CEW as in §4: o a Boolean :{0,1}n→ {0,1},CEW( ) = deg( ˜
)whe e ˜
is
he mul ilinea ex ension.
An obse e is simply an algo i hm; we anno a e i wi h wo esou ces:
• ime bound T(n),
• ep esen a ion bound B(n)con olling he maximal CEW o any in e media e mul i-
linea o m i ma e ializes (including ˜
i sel ).
We do no claim CEW alone bounds ime; he ime bound is pa o he model.
7.2 Epis emic classes (de ini ions ma ched o classical ones)
De ini ion 18 (Epis emicP).Epis emicP(n)is he se o :{0,1}n→ {0,1}compu able
by an obse e ha uns in ime nO(1) and whose in e media e CEW is bounded by nO(1).
Le Epis emicP := SnEpis emicP(n).
De ini ion 19 (Epis emicNP).Epis emicNP(n)is he se o :{0,1}n→ {0,1} o which
he e exis s a polynomial pand a e i ie unning in ime nO(1) such ha
(x)=1 ⇐⇒ ∃w∈ {0,1}≤p(n)V(x, w)=1,
and o each ixed w, he accep ance p edica e x7→ V(x, w)has CEW ≤nO(1).
Le Epis emicNP := SnEpis emicNP(n).
Rema k 16.(i) The ime bounds make he equali ies wi h classical classes s aigh o wa d
(see below). (ii) The CEW cons ain s eco d ha he ep esen a ions used by he obse e
a e low-deg ee (consis en wi h §2’s BP→SPDP and §4’s CEW analysis).
7.3 Basic ac s and equi alences
P oposi ion 55 (BP leng h ⇒CEW/e alua ion bounds).I a laye ed BP o leng h Land
wid h Wcompu es , hen CEW( )≤Land (x)can be e alua ed in poly(n, L, W) ime.
P oo . As in §4, P oposi ion 36; e alua ion is a single pa h agg ega ion o e Llaye s.
Theo em 56 (Epis emic–classical equi alence).
Epis emicP = P, Epis emicNP = NP.
P oo . P⊆Epis emicP: By §2.1, any P- ime decide compiles o a BP wi h L=nO(1); by
P oposi ion 55, CEW ≤nO(1) and ime emains polynomial.
Epis emicP ⊆P: By de ini ion, obse e s in Epis emicP un in polynomial ime; hence
he compu ed unc ions lie in P.
The NP case is iden ical: he e i ie uns in polynomial ime by de ini ion, so Epis emicNP ⊆
NP; con e sely any NP e i ie has low-deg ee accep ance p edica es (local checks), placing
i in Epis emicNP.
56
7.4 Hie a chy and sepa a ion in he epis emic iew
De ini ion 20 (Epis emicTIME/SPACE).Fo a unc ion :N→N,
Epis emicTIME[ (n)] := {L| ∃ obse e deciding Lin O( (n)) ime and wi h CEW ≤ (n)O(1) },
and simila ly o Epis emicSPACE by eplacing he ime bound wi h a space bound and
acking CEW as an auxilia y ep esen a ion budge .
Theo em 57 (Obse e hie a chy).PolyObsn⊊ExpObsn(as in §4, Theo em 42). Conse-
quen ly,
Epis emicP ⊊Epis emicNP,
wi nessed by he Lag angian/Tsei in amilies (§6/§14) whose ∂-ma ix (hence SPDP) ank
is 2Ω(n), implying CEW ≥Ω(n)(Co olla y 40).
7.5 Wha we do no claim
We do no asse a gene al “CEW ⇒ ime O(CEW3)” law. Time depends on he ep esen-
a ion model (e.g., BP, ABP, ci cui wi h bounded bo om suppo ). Ou ce i ied uppe
bounds come ia conc e e compila ions (BP→SPDP) and s uc u al lemmas (dep h/wid h/-
suppo ).
The “quan um obse e ” discussion is me apho ic and op ional; keep i as an in ui ion
box, no as a heo em.
Rema k 17 (Epis emic–quan um analogy).Replacing CEW by en anglemen measu es (e.g.,
Schmid ank/en anglemen en opy) sugges s analogies be ween classical epis emic inacces-
sibili y and quan um ad an age. We do no use his in any p oo he ein.
8 SPDP Theo y and Sepa a ion F amewo k
Rema k 18 (Pu pose o his sec ion).This sec ion o malizes he SPDP ank amewo k
ha unde lies all quan i a i e a gumen s in he pape . Reade s in e es ed only in he high-
le el sepa a ion may ea i as a echnical ounda ion connec ing he obse e - heo e ic
pe spec i e o he conc e e algeb aic p oo o P=NP.
8.1 SPDP as a ank measu e
Le Fbe a ield o cha ac e is ic 0o a su icien ly la ge p ime. Fo a mul ilinea polynomial
∈F[x1, . . . , xn]and an in ege ℓ≥0, de ine he o de -ℓshi ed pa ial-de i a i e ma ix
Mℓ( )as ollows:
•A ow is indexed by a pai (R, α)whe e R⊆[n]wi h |R|=ℓand αis a monomial wi h
deg(α)≤ℓ. The ow ec o is he coe icien ec o (in he ull mul ilinea monomial
basis on [n]) o he polynomial α·∂|R| /∂xR.
•The SPDP ank a o de ℓis kSPDP,ℓ( ) := ank(Mℓ( )).
We also w i e kSPDP( ) := maxℓ∈{2,3} kSPDP,ℓ( )when only ixed o de s ℓ∈ {2,3}a e
needed (as in §2).
57
•Fixed Π+=A,
•Two block schemes ecu ing ac oss all wo kloads: laye ed-wi es o NC1- ype ci -
cui s and ime× ape- iles o ROBP/DTM- ype aces.
In e e y case, hese genomes achie ed CEW = 1–2while p ese ing seman ic equi alence.
This empi ical egula i y e ealed ha locali y and basis choice—no global scheduling o
andomness—go e n he a ainable wid h.
In e p e i e summa y. Wi h adius-1 windows, each p oo ow “sees“ only a cons an
numbe o disjoin a iable windows pe laye ; by he pape ’s wid h⇒ ank easoning, he
ow-span embeds in o a bounded enso p oduc , so he SPDP ank is polynomial a (k, ℓ) =
Θ(log n). The EA did no p o e his esul di ec ly—i iden i ied he symme y class he
o mal cons uc ion mus ealize, which he de e minis ic so ing-ne wo k compile la e
en o ces. Bo om line: he EA disco e ed he in a ian ecipe ( adius-1 + diagonal basis
+Π+=A+ wo block empla es) ha became he key componen o he o mal P-side
compile and he holog aphic locali y p inciple used in he sepa a ion.
The obse ed in a iance o minimal CEW ac oss p oblem amilies sugges ed he exis ence
o a uni o m, de e minis ic compila ion empla e wi h polyloga i hmic con ex ual wid h.
Guided by his esul , he de e minis ic so ing-ne wo k compile (Theo em 64) was de-
i ed o ep oduce he same s uc u al locali y in a ully o mal, inpu -independen way.
The EA hus se ed as an empi ical p obe o he sea ch space, iden i ying he holog aphic
pa ame e s ha la e appea ed as in a ian s in he o mal p oo o he uppe bound.
Summa y. The EA expe imen s did no eplace ma hema ical p oo ; a he , hey p e-
dic ed he symme y class o he success ul cons uc ion. They poin ed di ec ly o he
holog aphic locali y p inciple unde lying he Holog aphic Uppe -Bound P inciple: e e y
polynomial- ime compu a ion admi s a adius-1, diagonal-basis holog aphic embedding wi h
polylog CEW, yielding he P-side polynomial SPDP ank bound.
10 Exponen ial SPDP Rank o he Pe manen
We now p o e ha he pe manen amily has exponen ially la ge SPDP ank, p o iding
he complemen a y lowe bound o he polynomial uppe bounds es ablished o P- ime
compu a ions (Theo em 64). The pe manen is #P-comple e [43], making i a na u al
candida e o ha dness sepa a ion.
Theo em 66 (Exponen ial SPDP ank o pe mn).Le X= (xi,j)1≤i,j≤nbe an n×nma ix
o inde e mina es o e a ield F(cha ac e is ic a bi a y). Le
pe mn(X) = X
σ∈Sn
n
Y
i=1
xi,σ(i).
64

Fo any in ege k∈ {0,1, . . . , n}, conside he SPDP pa ame e s (k, ℓ) = (k, 0) (i.e., o de
kde i a i es and no shi ). Then
Γk,0(pe mn)≥n
k.
In pa icula , o k=⌊n/2⌋we ha e
Γ⌊n/2⌋,0(pe mn)≥n
⌊n/2⌋= Θ2n
√n= 2Ω(n).
P oo . We p oceed in i e s eps.
1) SPDP se up (pa ame e s and he ow amily). We use he canonical SPDP de -
ini ion Γk,ℓ(p) = ankFMk,ℓ(p), whe e ows a e indexed by pai s (S, m)wi h |S|=kand
deg m≤ℓ, and he ow is he coe icien ec o o m·∂Spin he s anda d monomial basis.
He e we ake ℓ= 0, so no shi s (m≡1). Thus ou ow se is simply
Rk:= {∂Spe mn|S⊆[n],|S|=k, ∂S:= Y
i∈S
∂/∂xi,i}.
(We di e en ia e w. . . he diagonal a iables xi,i; any ixed choice o one a iable pe ow
would wo k, bu he diagonal is he cleanes .)
2) Closed o m o each ow ∂Spe mn.Fix S⊆[n],|S|=k. A summand Qn
i=1 xi,σ(i)
o pe mnsu i es unde ∂Si σ(i) = i o each i∈S, because we di e en ia e exac ly w. . .
he a iables xi,i o i∈S. The e o e,
∂Spe mn=X
σ∈Sn
σ(i)=i∀i∈SY
i/∈S
xi,σ(i).
Equi alen ly, w i ing T:= [n] Sand X[T, T] o he p incipal subma ix on ows/cols T,
∂Spe mn= pe m(X[T, T]).
In pa icula , he iden i y pe mu a ion on Tcon ibu es he wi ness monomial
mS:= Y
i/∈S
xi,i,
wi h coe icien 1.
3) Independence lemma (explici wi ness columns).
Lemma 67 (Disjoin -wi ness independence).Fo dis inc S, S′⊆[n]wi h |S|=|S′|=k,
he monomial mS=Qi/∈Sxi,i appea s in ∂Spe mnwi h coe icien 1, and does no appea in
∂S′pe mn. Consequen ly, he se {∂Spe mn:|S|=k}is linea ly independen .
65
P oo . We al eady saw mSappea s in ∂Spe mn(iden i y on T= [n] S). Suppose S′=S.
Then T′= [n] S′=T. Any monomial in ∂S′pe mnis o he o m Qi∈T′xi,τ(i) o some
pe mu a ion τo T′. Such a monomial ne e con ains any a iable om a ow i∈S′( hose
ows we e di e en ia ed away). Bu i S′=S hen he e exis s an index j∈S′ S. In
mS=Qi∈Txi,i we ha e j∈T(since j /∈S), so mScon ains he ac o xj,j. Tha ac o
canno appea in any monomial o ∂S′pe mn( ow jis in S′), hence mSis absen om
∂S′pe mn.
Thus, in he coe icien ma ix (columns indexed by monomials), each ow ∂Spe mnhas
a p i a e 1in he column mSand 0in ha column o all o he ows. This yields a diagonal
subma ix o size n
kwi h nonze o diagonal, p o ing linea independence.
4) Coun ing lemma (how many independen ows). The e a e exac ly n
ksubse s
S⊆[n]o size k. Lemma 67 shows hese n
k ows a e linea ly independen , hence
Γk,0(pe mn)≥n
k.
5) Choice o kand he exponen ial bound. Using he cen al binomial es ima e,
n
⌊n/2⌋= Θ2n
√n= 2n−1
2log2n+O(1) = 2Ω(n).
Choosing k=⌊n/2⌋yields he claimed exponen ial lowe bound. Mo e gene ally, o any
cons an ac ion k=⌊αn⌋wi h α∈(0,1),
Γk,0(pe mn)≥n
αn= 2H(α)n+o(n),
whe e H(α)is he bina y en opy; maximizing a α= 1/2gi es he s onges exponen .
Rema ks ( o p eemp e e ee ques ions). Why ℓ= 0 (no shi s) is enough. The
de ini ion o SPDP ank allows any ℓ≥0. P o ing a lowe bound o a subse o ows
(namely, he ℓ= 0 ows) al eady lowe -bounds he ull Γk,ℓ. Thus ixing ℓ= 0 yields a alid
(and simples ) exponen ial lowe bound.
Field independence / cha ac e is ic issues. The p i a e-monomial wi nesses mS
ha e coe icien +1 in ∂Spe mn, so no cancella ion a ises o e any ield. The a gumen wo ks
in a bi a y cha ac e is ic.
Choice o de i a i e a iables. We di e en ia ed w. . . he diagonal a iables xi,i.
Any ixed choice ha picks one designa ed a iable pe ow would wo k iden ically: he
wi ness o ow Sbecomes he p oduc o hose designa ed a iables o e T= [n] S, and
he same “p i a e-column” a gumen goes h ough.
Abou s onge cons an s (e.g., 0.52). The p oo abo e cleanly gi es Γk,0≥n
k=
2Ω(n)(bes cons an a k≈n/2). A e ined cons an 20.52nis es ablished in he nex sub-
sec ion using shi ed de i a i es (ℓ > 0) wi h an in e sec ion-design a gumen . Empi ical
esul s in Appendix D con i m hese bounds nume ically.
66
10.1 A Shi ed/In e sec ion SPDP Lowe Bound wi h Explici Con-
s an
We wo k o e a ield Fo cha ac e is ic 0(o su icien ly la ge). Le X= (xi,j)1≤i,j≤nbe an
n×nma ix o inde e mina es and
pe mn(X) = X
σ∈Sn
n
Y
i=1
xi,σ(i).
Pa ame e s and SPDP ma ix. Fix cons an s w∈(0,1) and α∈(0, w/2). Le
k:= ⌊wn⌋, ℓ := 1
4log n.
Recall he SPDP ma ix Mk,ℓ(p)(De ini ion 11) has one ow o each pai (S, m)wi h |S|=k
and deg m≤ℓ, con aining he coe icien ec o o m·∂Spin he s anda d monomial basis.
S ep 1: A la ge cons an -weigh amily wi h bounded in e sec ions. Le [n]
k
deno e he amily o k-subse s o [n]. A s anda d g eedy packing in he Johnson g aph gi es:
Lemma 68 (In e sec ion-bounded packing in [n]
k).Fix n∈N,k=⌊wn⌋wi h w∈(0,1),
and a pa ame e α∈(0, w). Then he e exis s a amily F ⊆ [n]
ksuch ha |S∩T| ≤ αn o
all dis inc S, T ∈ F and
|F| ≥ n
k
Pk
=⌈αn⌉k
n−k
k− ≥2(H(w)−β(w,α))n−O(log n),
whe e
β(w, α) := max
∈[αn,k]k
nH
k+n−k
nHk−
n−k= max
θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw
1−w.
He e H(x) = −xlog2x−(1 −x) log2(1 −x)is he bina y en opy, and he O(log n) e m
collec s S i ling- ype ac o s.
P oo . Le U=[n]
kbe he se o all k-subse s o [n]. Fo a ixed S∈U, he numbe o
T∈Uwi h |S∩T|= is
N =k
n−k
k− , = 0,1, . . . , k.
(Choose which elemen s o S emain in he in e sec ion, hen choose he emaining k−
elemen s ou o he n−kou side S.)
De ine he “ball” ( eally: hick shell union) o in e sec ion adius αn a ound Sby
Ball(S, α) := {T∈U:|S∩T| ≥ αn}.
67
I s size sa is ies
B(n, k, α) := |Ball(S, α)|=
k
X
=⌈αn⌉k
n−k
k− .(1)
We i s uppe bound B(n, k, α)asymp o ically. Using he s anda d en opy bounds o
binomials (de i ed om S i ling’s app oxima ion), o all 0≤ ≤m,
m
≤2mH( /m)·poly(m),
wi h a poly(m) ac o ha con ibu es only O(log m) o he exponen . Applying his o he
wo binomial ac o s in N and summing (1), we ob ain
B(n, k, α)≤
k
X
=⌈αn⌉2kH( /k)·poly(k)·2(n−k)H(k−
n−k)·poly(n−k).
The sum has a mos k+ 1 = O(n) e ms, so i is bounded (up o ano he poly(n) ac o )
by he la ges summand:
B(n, k, α)≤2β(w,α)n·poly(n),(2)
whe e
β(w, α) := max
∈[αn,k]k
nH
k+n−k
nHk−
n−k.
W i ing θ= /k ∈[α/w, 1] and using k=wn yields he al e na i e o m
β(w, α) = max
θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw
1−w.
(We will no need he exac maximizing θ; he exp ession makes he dependence anspa en .)
Nex , we lowe bound he size o an in e sec ion-bounded amily by g eedy packing:
ini ialize F ← ∅ and he a ailable se U′←U. While U′=∅: pick any S∈U′, add i
o F, and dele e i s ball U′←U′ Ball(S, α). By cons uc ion, he esul ing Fsa is ies
|S∩T| ≤ αn o all dis inc S, T ∈ F, and
|F| ≥ |U|
maxS|Ball(S, α)|=n
k
B(n, k, α).
Using n
k≥2H(w)n/poly(n)and he 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 p o es he claim.
68
F om packing o a ull- ank SPDP mino (and he ℓ < (w−α)nga e). Le k=⌊wn⌋
wi h w∈(0,1), ix α∈(0, w/2), and le F ⊆ [n]
kbe he in e sec ion-bounded amily gi en
by he packing lemma (so |S∩T| ≤ αn o all dis inc S, T ∈ F). Fo each S∈ F w i e
T= [n] Sand se
S:= ∂Spe mn= pe m(X[T, T]), mS:= Y
i∈T
xi,i.
As in he ℓ= 0 case, coe mS( S)=1. Mo eo e , i S=S′ hen e e y monomial o S
uses a iables only om ows in T, whe eas mS′con ains he diagonal ac o xj,j o e e y
j∈T′= [n] S′. In pa icula , o each j∈S′ Swe ha e j∈Tbu j /∈T′; hence o
u n a monomial o Sin o mS′one mus inse a leas one a iable om each such ow j.
The e o e he numbe o equi ed ow-inse ions is
|S′ S|=k−|S∩S′| ≥ k−αn = (w−α)n−O(1).
Now ix a shi budge ℓ∈N( he SPDP shi deg ee). I we en o ce
ℓ < (w−α)n, (⋆)
hen no deg ee-≤ℓshi asuppo ed on ows om Scan in oduce all he missing diagonal
ac o s needed o hi mS′when S′=S. Conc e ely,
coe mS′(a· S) = 0 o all S′=Swhene e deg a≤ℓand (⋆)holds.
On he o he hand, aking a≡1keeps coe mS(a· S) = 1. Thus, i we es ic he SPDP
ma ix Mk,ℓ(pe mn) o he |F| ows indexed by (S, aS)wi h aS≡1and o he |F| columns
indexed by {mS′:S′∈ F}, we ob ain a diagonal subma ix wi h uni diagonal. Hence his
subma ix has ull ank |F|, and
Γk,ℓ(pe mn)≥ |F|.
Combining wi h he packing bound yields he explici asymp o ic:
Γk,ℓ(pe mn)≥2(H(w)−β(w,α))n−O(log n)whene e ℓ < (w−α)n,
whe e
β(w, α) = max
∈[αn,k]k
nH
k+n−k
nHk−
n−k= max
θ∈[α/w,1] wH(θ) + (1 −w)Hw−θw
1−w.
Finally, aking any ixed cons an s w∈(0,1),α∈(0, w/2), and ℓ=⌈1
4log n⌉, condi ion
(⋆)holds o all su icien ly la ge n, so he mino (and hence he ank bound) ollows.
Co olla y 69. Fo any ixed w∈(0,1),α∈(0, w/2), and ℓ=⌈1
4log n⌉, he e is n0such
ha o all n≥n0and k=⌊wn⌋,
Γk,ℓ(pe mn)≥2(H(w)−β(w,α))n−o(n).
In pa icula , he lowe bound holds wi h loga i hmic shi deg ee and bounded pai wise in-
e sec ions.
69

Nume ical ins an ia ion wi h a ≥0.52 cons an . Take w= 1/2and α= 0.18 (which
sa is ies α < w/2 = 0.25). We compu e β(1/2,0.18) by e alua ing he maximum o e
θ∈[0.36,1]:
β(1/2,0.18) = max
θ∈[0.36,1] 1
2H(θ) + 1
2H(2 −2θ).
Nume ically, he maximum occu s nea θ≈0.82 and yields β(1/2,0.18) ≈0.4713. The e o e,
H(1/2) −β(1/2,0.18) ≈1−0.4713 = 0.5287.
Hence, o all su icien ly la ge n,
Γ⌊n/2⌋,⌈1
4log n⌉(pe mn)≥20.52n.
Rema k 21.This shi ed/in e sec ion cons uc ion p o ides an explici cons an 0.52 using
k=⌊n/2⌋and ℓ=O(log n), complemen ing he simple ℓ= 0 iden i y-mino p oo . The
ℓ= 0 p oo emains he co e lowe bound o he P s NP sepa a ion; his e ined bound
shows ha SPDP ank can be made explici wi h modes shi deg ee.
10.2 Disco e y o he Global God-Mo e
Abs ac . This subsec ion ecoun s how he Global God-Mo e eme ged empi ically om
e olu iona y-algo i hm sea ches, was e amed heo e ically as an in e sion o he holog aphic
locali y p inciple, and was ul ima ely o malized as a uni o m p ojec ion heo em exposing
exponen ial SPDP ank.
The no ion o a Global God-Mo e did no a ise as a o mal axiom bu as an empi ical and
concep ual syn hesis linking h ee independen h eads o his wo k: (1) he e olu iona y-
algo i hm (EA) sea ch o e SPDP in a ian s, (2) he heo e ical in e sion o he holog aphic
locali y p inciple, and (3) he algeb aic o maliza ion o iden i y mino s wi hin shi ed-pa ial
ma ices.
1. Empi ical obse a ion. The EA expe imen s desc ibed in Sec ion C (“Empi ical
Clues om E olu iona y Sea ch”, abo e; de ailed in Appendix H) consis en ly con e ged on
a ema kably simple con igu a ion: adius–1 locali y, a diagonal basis, a ixed ans o ma ion
Π+=A, and wo block empla es go e ning all polynomial- ime amilies. This pa e n
implied ha e e y bounded-CEW compu a ion could be ep esen ed as a enso p oduc o
cons an - adius local ac o s, gua an eeing polynomial SPDP ank. A i s , his was iewed
only as an in a ian o e icien compu a ion.
2. Concep ual in e sion. While analyzing he codimension-collapse lemma (Sec ion 20,
Lemma 116), i became e iden ha he same in a ian could be in e ed: i bounded
obse e s comp ess in o ma ion h ough adius–1 windows, hen unbounded sys ems mus
possess algeb aic componen s ha canno be comp essed in his way. The ques ion na u ally
eme ged: Is he e a single uni o m p ojec ion ha exposes his non-comp essibili y? This
ques ion was he seed o he God-Mo e idea.
70
3. Algeb aic ealiza ion. The answe ook he o m o a p ojec ion ϕn ha , when
applied o a ha d amily (such as pe mno he Tsei in polynomial), aligns i s shi ed pa ial
de i a i es so ha an iden i y block appea s explici ly inside Mk,ℓ(pn◦ϕn)a e sui able
eindexing. Wha began as a local symme y hus became a global p ojec ion heo em: a
single cons uc i e ans o ma ion e ealing an exponen ial independen se wi hin he SPDP
ma ix.
4. Syn hesis. This ealiza ion uni ied he wo hal es o he amewo k. On he P side,
he Wid h⇒Rank lemma (Lemma 15) p o ed ha all adius–1 compiled compu a ions ha e
polynomial SPDP ank. On he NP side, he newly disco e ed global p ojec ion— he God-
Mo e—p o ed ha ha d amilies necessa ily expose exponen ial SPDP ank unde he same
pa ame e s. Toge he hey o med he decisi e b idge leading o he uncondi ional sepa a-
ion.
5. In e p e i e pe spec i e. Wi hin he obse e - heo e ic eading o he N-F ame
model, he God-Mo e ep esen s he global alignmen o he obse e wi h he sys em’s ull
in o ma ional s uc u e— he poin a which e e y local bounda y becomes isible simul a-
neously. This “global p ojec ion o s uc u e” comple es he symme y be ween bounded
and unbounded obse e s, mi o ing he ma hema ical ole he God-Mo e plays in he
complexi y- heo e ic p oo .
10.3 Global P ojec ion (“God Mo e”): Iden i y Mino o Mk,0(pe mn)
De ini ion 21 (Global P ojec ion / God-Mo e).Le {pn}be a amily o polynomials pn∈
F[x1, . . . , xN(n)]and ix pa ame e s k, ℓ ∈N. We say ha {pn}admi s a Global P ojec ion
(God-Mo e) a (k, ℓ)i he e exis , uni o mly in n:
•a a iable p ojec ion ϕn:F[x1, . . . , xN(n)]→F[y1, . . . , yM(n)] ha is linea (a ine is
also allowed a e homogeniza ion),
•in e ible ow/column eindexings Pn, Qn(pe mu a ion/block-in e ible ma ices),
such ha he shi ed-pa ial ma ix con ains an iden i y block o size R(n):
PnMk,ℓ
pn◦ϕnQn⊇IR(n).
Equi alen ly,
ankFMk,ℓ
pn◦ϕn≥R(n).
We call R(n) he e ealed iden i y size. In ou applica ions R(n) = nΩ(log n)(o en R(n) = n
k
wi h k= Θ(log n)).
Rema k 22 (Coe icien -space o mula ion).Equi alen ly, he e exis s a uni o m column map
Πnac ing on he coe icien space (monomial basis) and a uni o m ow selec ion Snsuch ha
Mk,ℓ(pn)Sn,∗Πn=IR(n).
Thus Mk,ℓ(pn)con ains an iden i y mino o size R(n). This is basis-independen by Lemma 20(d).
71
Theo em 70 (Exis ence o he God-Mo e o he ha d amily).The e is an explici ha d
amily {hn}(e.g. he pe manen pe mno a Tsei in/expande -based CNF polynomial) and
cons an s c0, c1>0such ha o
k=c0log n, ℓ =c1log n,
he amily {hn}admi s a Global P ojec ion (God-Mo e) a (k, ℓ)wi h e ealed iden i y size
R(n) = nΩ(log n).
Mo eo e , he p ojec ion ϕnand he eindexings Pn, Qna e uni o mly compu able in ime
poly(n).
Rema k 23 (P oo o e iew).Cons uc ϕnso ha he (k, ℓ)-shi ed-pa ial ows index a
s uc u ed se o pa ials wi h disjoin p i a e monomials and ze o c oss-in e e ence a e
eindexing— his exposes IR(n)as a p incipal subma ix (an iden i y mino ). Fo he pe ma-
nen , use he s anda d mino /iden i y-mino ex ac ion unde a combina o ial p ojec ion; o
Tsei in, use he expande incidence s uc u e o isola e disjoin local cons ain s. Uni o mi y
ollows om he explici combina o ial ule o ϕnand om index maps ha depend only
on (n, k, ℓ). The de ailed cons uc ion o pe mnis gi en in Theo em 72 below.
Co olla y 71 (Exponen ial SPDP lowe bound).Unde he hypo heses o Theo em 70,
Γk,ℓ(hn) = ankFMk,ℓ(hn)≥R(n) = nΩ(log n).
Rema k 24 (Use in he sepa a ion).The God-Mo e is used only on he NP side o ob ain
he exponen ial lowe bound (Co olla y 71). The P side does no use he God-Mo e: i elies
on he Wid h⇒Rank lemma (Lemma 15) o show Γk,ℓ(p) = nO(1) o all p∈Pa he same
pa ame e egime k, ℓ = Θ(log n). Combining he wo bounds yields he sepa a ion.
Theo em 72 (Global p ojec ion / “God Mo e” o pe mn).Fix n≥1and k∈ {0, . . . , n}.
Le Mk,0(pe mn)be he SPDP ma ix (De ini ion 11) whose ows a e ∂Spe mnwi h |S|=k
(no shi s, ℓ= 0), exp essed in he s anda d monomial basis o F[xi,j]1≤i,j≤n. De ine he n
k
“wi ness monomials”
mS:= Y
i∈[n] S
xi,i (S⊆[n],|S|=k).
Le Cn:= {mS:|S|=k}. The e is a uni o m, polynomial- ime compu able p ojec ion
Πn:Monomials −→ FCn,Πn(monomial u) = (1{u=mT})T:|T|=k,
such ha
ΠnMk,0(pe mn) = I(n
k)
a e o de ing ows/columns compa ibly wi h {S}and {mT}.
Consequen ly, Mk,0(pe mn)has ank a leas n
k. Fo k=⌊n/2⌋ his gi es Γk,0(pe mn)≥
n
⌊n/2⌋= 2Ω(n).
72
P oo . 1) Explici ow amily and wi ness monomials. Rows a e S:= he coe icien
ec o o ∂Spe mn o |S|=k, whe e
∂Spe mn=X
σ∈Sn
σ(i)=i∀i∈SY
i∈[n] S
xi,σ(i)= pe m(X[T, T]), T = [n] S.
In pa icula , he iden i y pe mu a ion on Tcon ibu es he monomial
mS=Y
i∈T
xi,i
wi h coe icien +1 in ∂Spe mn.
I S′=S, hen T′= [n] S′=T. Any monomial in ∂S′pe mnuses a iables only om
ows indexed by T′. Since mScon ains xj,j o some j∈T T′=S′ S, he monomial mS
canno appea in ∂S′pe mn. Hence:
coe mT(∂Spe mn) = (1i T=S,
0i T=S. (⋆)
2) Uni o m p ojec ion Πn.De ine Πn o ze o ou all monomial columns excep hose
in Cn={mT}, keeping he Cn-coo dina es in he ixed o de (mT)|T|=k. Equi alen ly, Πn
is he coo dina e p ojec ion on o he Cn-indexed subspace. This map is uni o m in nand
compu able in ime poly(n): ecognizing whe he a monomial equals some mTamoun s o
checking whe he i is exac ly he p oduc o diagonal a iables {xi,i :i∈[n] T} o a
unique To size k.
Applying Πn o he column space o Mk,0(pe mn)simply eads o , o each ow S, he
coe icien ec o es ic ed o Cn. By (⋆), he es ic ed ow is he s anda d basis ec o
eS∈FCn. The e o e
ΠnMk,0(pe mn) = I(n
k),
and he ank is a leas n
k. Choosing k=⌊n/2⌋gi es 2Ω(n).
PAC-compile o m (uni o m ealizabili y). Le PAC.compile(n, k)emi code o Πn
as ollows:
•Inpu : a monomial udesc ibed by i s mul ise o (i, j)indices.
•Tes : check uhas deg ee n−kand consis s only o diagonal a iables {xi,i}; i no ,
ou pu he all-ze o ec o in FCn.
•Map: i yes, compu e T= [n] {i:xi,i |u}and e u n eT∈FCn.
This is O(n) ime gi en a spa se monomial ep esen a ion. Thus Πnis a uni o m, poly ime
p ojec ion—exac ly he “God Mo e” you wan : a single, explici map ha isola es an iden i y
block o all ows simul aneously.
73
Ve i ica ion: The e exis s a polynomially bounded obse e Vsuch ha , o each n,V
e i ies pn ia a polynomial-leng h wi ness (Epis emicNP), mi o ing he classical NP e i ie
(Theo em 8.2).
12.2 Uni ied encapsula ion
Each obse e Opackages bo h un ime and CEW cons ain s alongside i s ansi ion unc-
ion. This a oids ci cula i y: all bounds a e pa o he objec being easoned abou , and he
sepa a ion is p o ed using algeb aic ank ce i ica es independen o O’s beha io (§§2.7–2.8).
12.3 Modula i y
The classes Epis emicP and Epis emicNP euse he same obse e no ion, di e ing only
by exis en ial wi nesses; §8 shows Epis emicP = Pand Epis emicNP = NP ( e minology
alignmen ), wi hou being used as p emises o he sepa a ion.
12.4 Epis emic in e p e a ion ( ema k)
The ank-based seman ics (SPDP) align in e en ial capaci y (CEW) wi h compu a ional
cos : low ank co esponds o polynomial obse e s; he explici amily o ces exponen ial
ank, escaping any polynomial obse e .
12.5 Ex ensibili y ( ema k)
The obse e abs ac ion admi s ca ego ical o model- heo e ic e inemen s (e.g., mo phisms
as esou ce-bounded simula ions), bu hese a e no needed o he p esen p oo s.
13 Fo mal Equi alence, Assump ion In en o y, and Ve -
i ica ion Audi
This sec ion eco ds he logic-le el closu e o he amewo k, he exac lis o assump ions
used (g ouped by ype), and he end- o-end e i ica ion audi . I is independen o imple-
men a ion de ails and can be ead s andalone.
13.1 Fo mal Equi alence Theo em
We o malize he equi alence be ween he obse e - heo e ic sepa a ion and he classical
ZFC s a emen P=NP.
De ini ion 22 (CEW-based sepa a ion).The e exis s a language Lwi h L∈NP P,
and, o all su icien ly la ge n, e e y polynomially bounded obse e O(bounded ime and
bounded CEW/ ep esen a ion deg ee) ails o compu e some explici high- ank cha ac e is ic
unc ion ⋆
n:{0,1}n→ {0,1}sa is ying kSPDP,ℓ( ⋆
n)≥2Ω(n)( ixed ℓ∈ {2,3}).
We w i e his me a-s a emen as CEWBasedSepa a ion.
80

De ini ion 23 (ZFC p oo s a emen ).
ZFCP oo := (P=NP)
in he s anda d Tu ing-machine model.
Theo em 79 (Fo mal Equi alence).
CEWBasedSepa a ion ⇐⇒ ZFCP oo .
P oo . Fo wa d (⇒). CEWBasedSepa a ion asse s he exis ence o L∈NP P; hence
P=NP. No u he assump ions a e equi ed.
Backwa d (⇐). Assume P=NP. Then he e exis s L∈NP P. By he s anda d
polynomial- ime e i ie o L, he cha ac e is ic polynomial amily {pn}(e.g., Lag angian/T-
sei in encodings) admi s polynomial- ime e i ica ion. F om §2.6–§2.7 and §2.3–§2.6, we ha e
exponen ial lowe bounds kSPDP,ℓ(pn) = 2Ω(n)de i ed ia pa ial-de i a i e ans e s and he
SPDP subma ix b idge. The de e minis ic dual cons uc ion wn∈V⊥
n(c . §2.7) sepa a es
any compiled polynomial- ime amily om {pn}, so e e y polynomially bounded obse e
ails o compu e pnon some ixed shi /index. Thus CEWBasedSepa a ion holds.
Rema k 28.The p oo uses only al eady-es ablished ac s: (i) BP→SPDP polynomial uppe
bounds o P(§2.1), (ii) exponen ial SPDP lowe bounds o he explici amily (§§2.3–2.6
and §6), and (iii) he de e minis ic wn∈V⊥
ncons uc ion (§2.7). No addi ional hypo heses
a e in oduced he e.
13.2 Assump ion In en o y (all p o ed ea lie )
Fo con enience we lis he main s uc u al ac s used in he inal sepa a ion. Each i em is
p o ed ea lie in he pape ; no addi ional axioms beyond ZFC a e assumed.
(A1) Boolean–polynomial co espondence. E e y :{0,1}n→ {0,1}has a unique
mul ilinea ep esen a ion o e a ield Fo cha ac e is ic 0o su icien ly la ge p ime. This
is s anda d mul ilinea ex ension o e ini e ields.
(A2) SPDP subma ix b idge. Fo mul ilinea pand any pa i ion [n] = S⊔T,PDS,T (p)
occu s (up o anspose and column es ic ion) as a subma ix o he o de -ℓSPDP ma ix;
hence ank(PDS,T (p)) ≤ kSPDP,ℓ(p). P o ed in he main body ia di ec cons uc ion.
(A3) Explici ha d amily. The Lag angian/Tsei in (o #3SAT) amily {pn}sa is ies
ank(PDSn,Tn(pn)) = 2Ω(n) o some |Sn| ≤ ℓ, implying kSPDP,ℓ(pn) = 2Ω(n). P o ed ia
explici cons uc ion and ank analysis.
(A4) P-side compila ion and ank uppe bound. E e y L∈Pcompiles o a laye ed
BP o polynomial leng h/wid h, o equi alen ly admi s a adius-1compiled ep esen a ion
wi h CEW(p)≤C(log n)c; he Wid h⇒Rank heo em hen gi es kSPDP,ℓ(χL)≤nO(1).
P o ed ia he de e minis ic compile cons uc ion and p o ile coun ing lemmas.
81
(A5) De e minis ic dual / annihila o . Fo he compiled P-side ow span Vn, he e
is a de e minis ic polynomial- ime p ocedu e p oducing wn∈V⊥
n= 0 ha anishes on all
compiled ows ye de ec s some ow o he ha d amily. P o ed ia dual cons uc ion and
o hogonali y a gumen .
Analy ic ac s. S anda d ma hema ical ac s a e used h oughou :
•Ma ix- ank mono onici y: Subma ix ank ne e exceeds ambien ank; ank is
de ec ed by nonze o mino s.
•Exponen ial dominance: 2αn e en ually domina es e e y polynomial nc o any
cons an s α > 0,c > 0.
•Fini e- ield coun ing (op ional): S anda d ank- ail bounds o andom ma ices
o e Fqwhen used o show low- ank se s ha e exponen ially small densi y.
Toge he , (A1)–(A5) and he analy ic ac s imply he main sepa a ion heo em P=NP.
No conjec u al complexi y hypo heses a e used (no #ETH, SETH, e c.); all lowe
bounds a e algeb aic and uncondi ional.
13.3 Ve i ica ion Audi (End- o-End)
This audi summa izes how he p oo is checkable and non-ci cula :
Objec le el. All inpu s a e ini e objec s ( ini e g aphs/BPs, ini e coe icien ec o s,
ini e ma ices), o malizable in ZFC; anks and spans a e decided by ini e linea algeb a.
Uppe s. lowe sepa a ion.
•P-side: BP→SPDP yields kSPDP,ℓ ≤nO(1) o all χL,L∈P.
•Ha d side: Explici amily {pn}has kSPDP,ℓ = 2Ω(n).
De e minis ic dual cons uc ion. The nonze o wn∈V⊥
nis ob ained by de e minis-
ic linea -algeb aic p ocedu es (e.g., Ba eiss/Rank- e ealing elimina ion) on a ini e ma ix
assembled om a cons an -size shi scheme; bi -complexi y is polynomial.
Decision packaging (no ci cula i y). E alua ion om a low- ank ce i ica e (when
needed) uses only he p o ided ac o iza ion and a ixed linea ex ac o ; i ne e que ies
as an o acle.
Ba ie compa ibili y.
•Non- ela i iza ion: Algeb aic SPDP lowe bounds pe sis ela i e o o acles; he
P-side uppe bound need no ela i ize.
•Non-na u ali y: Low SPDP ank has exponen ially small densi y; u h- able con-
s uc i i y in poly(n) ails o size easons (§2.8).
82
Ou come. The sepa a ion is a composi ion o ini e algeb aic s eps (compila ion, ank
bounds, subspace dualiza ion). E e y dependency is explici and checkable; he e a e no
hidden assump ions o p obabilis ic s eps equi ed o co ec ness.
14 Examples o CEW Compu a ion
(Illus a i e obse e beha iou s in he CEW amewo k)
Rema k 29 (Pu pose).This sho sec ion gi es h ee conc e e, sel -con ained examples—
Pa i y, AND, and Majo i y— o make he Con ex ual En anglemen Wid h (CEW) no ion
om §§4 and 6 angible. These examples a e illus a i e; no hing new is assumed o equi ed
o he main esul s.
14.1 Se up and CEW con en ion
An obse e O= (S, s0, δ, ω)p ocesses a leng h-ninpu x∈ {0,1}nle - o- igh . Le R ⊆S
be he se o s a es eachable a e exac ly s eps o e all leng h- p e ixes (i.e., o e all
inpu s o leng h ). We ake he CEW o Oon leng h ninpu s as
CEWn(O) := max
0≤ ≤n|R |.
(Equi alen ly, wo s -case o e inpu s and ime; his aligns wi h he “wid h = numbe o
simul aneously dis inguishable s a es” in ui ion used h oughou he pape .)
14.2 Pa i y
Task. Compu e PARITYn(x)=1i Pixi≡0 (mod 2).
Obse e .
•S={e en,odd},s0= e en.
•δ(e en,0) = e en,δ(e en,1) = odd;
δ(odd,0) = odd,δ(odd,1) = e en.
•ω(e en) = Accep ,ω(odd) = Rejec (o de e ou pu o =n).
CEW calcula ion.
• = 0:R0={e en}⇒|R0|= 1.
• ≥1: bo h li e als may appea , so R ={e en,odd}⇒|R |= 2.
Thus CEWn(Opa i y) = 2 o all n.
83
14.3 AND
Task. Compu e ANDn(x) = 1 i Vn
i=1 xi= 1.
Obse e . S a es ack he leng h o he longes all-ones p e ix plus a sink:
S={s0, s1, . . . , sn−1, ejec }, s0ini ial.
T ansi ions: o i<n−1,
δ(si,1) = si+1, δ(si,0) = ejec ; δ( ejec , b) = ejec .
Final s ep: δ(sn−1,1) = sn−1(o mo e o a dis inc accep i p e e ed); ou pu ω(sn−1) =
Accep , o he s Rejec .
CEW calcula ion. A e s eps, he all-ones p e ix leng h can be any i∈ {0,...,min( , n−
1)}, and i any ze o appea ed, he un is in ejec .
Hence R ={s0, . . . , smin( ,n−1)}∪{ ejec }, so |R |= min( + 2, n + 1).
Thus CEWn(Oand) = n+ 1.
(I one p e e s a dis inc accep s a e a s ep n, he bound emains Θ(n); coun ing de ails
change by a mos +1.)
14.4 Majo i y
Task. Fo odd n= 2k+ 1, compu e MAJn(x)=1i Pixi≥k+ 1.
Obse e . T ack he unning di e ence #{1}−#{0}clipped o [−k, k]:
S={−k, −k+ 1,...,0, . . . , k −1, k}, s0= 0.
T ansi ions: δ(s, 1) = min(s+ 1, k),δ(s, 0) = max(s−1,−k).
Ou pu a =n:ω(s) = Accep i s > 0(s ic majo i y).
CEW calcula ion. A e s eps, he unclipped di e ence lies in [−( ), ]; clipping o
[−k, k]gi es
R =−min( , k),−min( , k)+1, . . . , min( , k).
Thus |R |= 2 min( , k)+1, maximized a ≥kwi h alue 2k+ 1 = n.
Hence CEWn(Omaj) = n.
14.5 Takeaway
These examples exhibi he in ended beha iou o CEW:
•Cons an CEW (Pa i y): bounded, inpu -leng h independen compu a ion.
•Linea CEW (AND, Majo i y): he obse e mus dis inguish Θ(n)in e media e
con ex s, ma ching he in ui i e g ow h o “s a e-space wid h”.
They p o ide conc e e ancho s o he abs ac CEW de ini ions and a e consis en wi h he
hie a chy esul s in §4 (and he obse e /classical co espondences in §6).
84
15 The Pe manen Func ion and he #3SAT Cha ac e -
is ic Polynomial
This sec ion supplies comple e, sel -con ained lowe bounds on SPDP ank o wo canonical
amilies:
1. he pe manen polynomial on n×n a iables, and
2. he #3SAT cha ac e is ic polynomial associa ed wi h 3-CNF o mulas.
Fo he pe manen we gi e a ull p oo om i s p inciples. Fo #3SAT we s a e he
p ecise lowe bound and gi e a s uc u ally explici p oo ske ch, hen in oke he Pa ial-
De i a i e ⇒SPDP b idge om §2.3–§2.6 (Theo em 17 and Co olla y 18 in you d a ) o
conclude he SPDP bound.
Th oughou , SPDP ank a o de kdomina es he classical pa ial-de i a i e ank o all
k-o de ∂-ma ices (Theo em 17), so an exponen ial ∂- ank lowe bound a some k= Θ(n)
immedia ely yields an exponen ial SPDP ank a he same o de .
15.1 The pe manen polynomial
Le X= (xi,j)1≤i,j≤nbe an n×nma ix o a iables. The pe manen is
Pe mn(X) := X
σ∈Sn
n
Y
i=1
xi,σ(i).
We ega d Pe mnas a mul ilinea polynomial in he n2 a iables {xi,j}. Fo a se S⊆[n]×[n]
o a iable indices, w i e ∂S:= Q(i,j)∈S
∂
∂xi,j o he mixed pa ial de i a i e.
Lemma 80 (De i a i es = mino s o complemen s; exac o m).Fix an in ege kwi h
0≤k≤n. Le R, C ⊆[n]be ow/column se s wi h |R|=|C|=k. Fo any bijec ion
π:R→C, le
Sπ:= {(i, π(i)) : i∈R}.
Then
∂SπPe mn(X) = Pe mn−kX[Rc, Cc],
i.e., he (n−k)×(n−k)p incipal complemen mino pe manen on he emaining ows Rc
and columns Cc. I S⊆[n]×[n]is no he g aph o a pa ial ma ching (i.e., wo pai s in S
sha e a ow o a column), hen ∂SPe mn≡0.
P oo . Expand Pe mnas a sum o e σ∈Sn. A monomial Qixi,σ(i)su i es ∂Sπi o all
i∈Rwe ha e σ(i) = π(i). This pins σon R, and he emaining ac o is he pe manen o
he subma ix indexed by Rc×Cc. I Sis no a ma ching, no pe mu a ion uses all a iables
o S, so he de i a i e is ze o.
Lemma 81 (Dis inc complemen s ⇒disjoin suppo s ⇒independence).Fix k. Fo each
pai o se s R, C ⊆[n]wi h |R|=|C|=k, de ine
pR,C(X) := Pe mn−kX[Rc, Cc].
85

Then he amily {pR,C}|R|=|C|=kis linea ly independen o e any ield: each pR,C in ol es
only he a iables indexed by Rc×Cc, and o dis inc pai s (R, C)= (R′, C′) hese suppo s
a e disjoin .
P oo . I (R, C)= (R′, C′), hen he se s o emaining indices di e , so he wo polynomials
a e unc ions o disjoin se s o a iables; a non i ial linea combina ion could no cancel
monomials ha li e on disjoin a iable se s. Hence he amily is linea ly independen .
P oposi ion 82 (Many independen k- h de i a i es).Fo ixed k, he ec o space spanned
by he o de -kpa ial de i a i es {∂SPe mn:|S|=k}has dimension a leas
n
k2
.
P oo . By Lemma 80, e e y ma ching Sπ(wi h π:R→C,|R|=|C|=k) yields ∂SπPe mn=
pR,C. Di e en bijec ions πwi h he same pai (R, C)gi e he same polynomial pR,C; di e en
pai s (R, C)gi e di e en polynomials (Lemma 81). The numbe o dis inc pai s is n
k2.
The e o e he span has dimension a leas n
k2.
Theo em 83 (Exponen ial pa ial-de i a i e lowe bound o he pe manen ).Le k=
⌊n/2⌋. Then
dimspan{∂SPe mn:|S|=k}≥n
k2
= 2Ω(n).
P oo . Immedia e om P oposi ion 82 and he s anda d bound n
⌊n/2⌋= 2n(1−o(1)).
Co olla y 84 (Exponen ial SPDP ank o he pe manen a o de k).Le k=⌊n/2⌋. The
o de -kSPDP ank o Pe mnsa is ies
kSPDP,k(Pe mn)≥n
k2
= 2Ω(n).
P oo . By he b idge (Theo em 17 / §2.6 in you d a ), o e e y pa i ion [n2] = S⊔T
wi h |S|=k(he e he g ound se is he n2 a iable posi ions), he classical pa ial-de i a i e
ma ix embeds (up o anspose) as a subma ix o he o de -kSPDP ma ix. Hence he
SPDP ank a o de kis a leas he o de -kpa ial-de i a i e ank. Apply Theo em 83.
Rema k 30 (Wha o de we use).The P-side uppe bounds in §2.1 ix ℓ∈ {2,3}. Fo lowe
bounds, i su ices o show ha o some o de k= Θ(n) he SPDP ank is exponen ial;
his al eady sepa a es he low- ank nO(1) wo ld om he 2Ω(n)wo ld. No ension a ises om
using di e en de i a i e o de s on he wo sides.
15.2 The #3SAT cha ac e is ic polynomial
Le φbe a 3-CNF on a iables x1, . . . , xn. De ine he cha ac e is ic 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 mul ilinea and ag ees wi h he indica o o sa is ying assignmen s on
{0,1}n.
We s a e an explici exponen ial lowe bound o a s anda d explici amily o o mulas
(e.g., Tsei in con adic ions on cons an -deg ee expande s wi h a single pa i y lip, o he
Lag angian/Tsei in encodings e e enced in you §6/§14), and hen p o e he SPDP conse-
quence by appealing o he pa ial-de i a i e →SPDP b idge.
Theo em 85 (∂-ma ix lowe bound o #3SAT encodings; explici amily).The e exis s
an explici amily {φn}o 3-CNFs on n a iables (e.g., Tsei in/expande encodings, see §6
/ §14) and a sequence o pa i ions [n] = Sn⊔Tnwi h |Sn|= Θ(n)such ha he classical
pa ial-de i a i e ma ix sa is ies
ankPDSn,Tn(χφn)= 2Ω(n).
P oo . We summa ise he a gumen de eloped in Sec ions 6 and 14 o he Lag angian/T-
sei in amily, specialising i o he cha ac e is ic polynomials χφn.
Le {Gn}be a amily o bounded-deg ee Ramanujan (o mo e gene ally spec al-expande )
g aphs and le {φn}deno e he associa ed Tsei in o #3SAT encodings on Gn. Sec ion 6
cons uc s, o each n, a pa i ion o he a iable se in o wo blocks Sn⊔Tnwi h |Sn|= Θ(n)
such ha he pa ial-de i a i e coe icien ma ix
PDSn,Tn(χφn)
con ains a la ge, well-condi ioned combina o ial design mino .
Conc e ely, by he expande ball-packing lemma (Sec ion 6.3), one can choose Θ(n)
disjoin e ex neighbou hoods U1, . . . , Umin Gnwhose closed neighbou hoods a e pai wise
disjoin . Fo each Uiwe de ine:
•a mixed pa ial ∂τi aking one de i a i e pe cons ain in Ui( ow index), and
•a monomial xαi ha selec s one inciden edge pe e ex in Ui(column index).
The cons uc ion in Sec ion 6 shows: (i) he suppo s o he monomials xαia e pai wise
disjoin , and (ii) in he en y o PDSn,Tn(χφn)indexed by ow τiand column αj, we ha e
∂τiχφnxαj=(±1, i =j,
0, i =j,
because he neighbou hoods N[Ui]and N[Uj]a e disjoin whene e i=j. Hence he sub-
ma ix on he selec ed ows and columns is a signed iden i y ma ix o size exp(Ω(n)), and
i s ank is he e o e exp(Ω(n)).
This es ablishes
ank PDSn,Tn(χφn) = 2Ω(n)
o he indica ed choice o Snand Tn, comple ing he p oo . All s eps a e pu ely combina o ial
and a e ca ied ou in de ail in Sec ions 6 and 14; we only summa ise he s uc u e he e.
This heo em is you pape ’s explici lowe -bound engine (de eloped ea lie ). I is e e -
enced he e only o connec i o SPDP ia he b idge.
87
Co olla y 86 (Exponen ial SPDP ank o χφna o de |Sn|).Wi h {φn}and {Sn}as in
Theo em 85 and kn:= |Sn|= Θ(n),
kSPDP, kn(χφn)≥2Ω(n).
P oo . By Theo em 17 / §2.6, PDSn,Tn(χφn)is ( anspose o ) a subma ix o he o de -|Sn|
SPDP ma ix o χφn. The e o e i s ank lowe bound ans e s e ba im.
15.3 Consequences and posi ioning
Two explici exponen ial wi nesses. Co olla y 84 (Pe manen ) and Co olla y 86 (#3SAT
encodings) u nish explici amilies wi h exponen ial SPDP ank a o de k= Θ(n).
Compa ibili y wi h he P-side. The P-side uppe bound (§2.1) shows o ixed ℓ∈ {2,3}
he SPDP ank o e e y P- ime language is nO(1). Ou lowe bounds need only show ha a
some o de k= Θ(n), he ank blows up o 2Ω(n) o explici NP- ype amilies, which hey
do.
B idge cen ali y. The embedding o classical ∂-ma ices as li e al subma ices o he
SPDP ma ix (Theo em 17 and §2.3) is he linchpin ha u ns known/al eady-p o ed ∂- ank
lowe bounds (pe manen ; you §6 Lag angian/Tsei in) in o SPDP lowe bounds wi hou
u he wo k.
Ba ie compliance. The a gumen s he e a e algeb aic and compa ible wi h known ba -
ie s (mono one es ic ions, dep h-4). They do no assume o equi e any non- ela i izing
p inciple; see §2.4 o ba ie immuni y.
Minimal c oss- e e ences ( o include in he compiled pape )
•B idge: §2.3 (Lemma 14) and §2.6–§2.7 (Theo em 17 + Co olla y 18) — ∂-ma ix
embeds in o SPDP; uni o m mono onici y in he o de pa ame e .
•Tsei in/Lag angian de elopmen : §6 (o §14.x in you cu en d a ) — explici
∂- ank 2Ω(n) o #3SAT encodings.
•P-side uppe bound: §2.1 (B anching-P og am ou e) — ixed-o de ℓ∈ {2,3}gi es
ank nO(1) o all L∈P.
These a e he only dependencies his sec ion uses.
16 Boolean Func ion Encoding
This sec ion ixes no a ion o u ning Boolean unc ions in o mul ilinea polynomials on
which we apply SPDP. I also cla i ies he (non-) ela ionship o he pe manen , a oiding a
common pi all (decision s. coun ing).
88
Rema k 31 (Didac ic pu pose).This sec ion is p ima ily pedagogical: i illus a es how
Boolean and a i hme ic ep esen a ions align wi hin he SPDP amewo k, p o iding he
concep ual b idge be ween decision unc ions and hei algeb aic encodings used in p e ious
and la e sec ions.
16.1 Boolean →mul ilinea in e pola ion
De ini ion 24 (Mul ilinea in e pola ion / “cha ac e is ic” polynomial).Fo a Boolean unc-
ion :{0,1}n→ {0,1}, i s mul ilinea in e pola ion p ∈F[x1, . . . , xn]is
p (x) := X
a∈{0,1}n: (a)=1 Y
i:ai=1
xiY
j:aj=0
(1 −xj).(6)
Then p is mul ilinea and sa is ies p (a) = (a) o e e y a∈ {0,1}n.
P oo (s anda d). Each summand is he indica o polynomial χa(x) = Qixai
i(1 −xi)1−ai,
which equals 1a x=aand 0a all o he Boolean poin s. Summing χao e he 1-inpu s o
gi es (6) and he Boolean ag eemen .
Rema k 32 (Uniqueness).Mul ilinea i y plus Boolean ag eemen de e mines p uniquely:
any wo mul ilinea polynomials ag eeing on all 2nBoolean poin s a e equal coe icien -wise.
16.2 Canonical encodings o SAT and #SAT
Le φbe a 3-CNF on a iables x1, . . . , xn. De ine he decision cha ac e is ic 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 he Boolean cube. This is he objec used in ou SPDP lowe
bounds o SAT- ype languages (decision iewpoin ).
I one wishes o coun sa is ying assignmen s (#SAT) as a single numbe , use he gene -
a ing polynomial e alua ed a a speci ic poin (e.g., Paχa(x)a x= (1,...,1)), o in oduce
an auxilia y a iable. We do no need ha he e; ou lowe bounds a ge χφas in (7).
16.3 A no e on he pe manen (decision s. coun ing)
Fo an n×ninde e mina e ma ix X= (Xi,j), he pe manen polynomial is
pe mn(X) = X
σ∈Sn
n
Y
i=1
Xi,σ(i).(8)
On a Boolean ma ix M∈ {0,1}n×n,pe mn(M)equals he numbe o pe ec ma chings (a
#P quan i y). By con as , he decision p edica e
pe m>0
n(M) := 1[pe mn(M)>0]
has he in e pola ion polynomial p pe m>0
ngi en by (6); i equals 1i a pe ec ma ching
exis s, and 0o he wise.
89
B idge B (de e minan al ba ie ⇒global ank). I pocke wise composi ion yields
block-diagonal A(P), hen
log de (I+θA(P)) = X
∈S
log de (I+θA(Q )) ≥δ|S|
o some δ > 0, while log de (I+θA)≤ k(A) log(1+θ∥A∥). Hence k(A)≳|S|, ans e ing
o an SPDP ank lowe bound ia mono one compila ion. Thus he a ia ional pic u e
ep oduces he pocke -packing lowe bound o §14.1.
Rema k 34 (Edi o ial no e).This subsec ion is explana o y; all quan i a i e lowe bounds
we use a e al eady supplied by §§14.1 and 14.3.
17.3 #3SAT SPDP lowe bound (di ec combina o ial p oo )
We now gi e a s and-alone lowe bound ha depends only on he algeb a o sa is ying
assignmen s.
Theo em 95 (#3SAT SPDP lowe bound).Le φbe a 3-CNF on n a iables wi h a leas
k≥2n/2sa is ying assignmen s. Le χφbe i s cha ac e is ic mul ilinea polynomial. Then
o e any ield o cha ac e is ic 0o su icien ly la ge p ime,
kSPDP, ℓ(χφ)≥2Ω(n)
o any ixed ℓ≥1; in pa icula kSPDP, ℓ(χφ)≥k≥2n/2.
P oo . W i e
χφ(x) = X
a∈{0,1}n:φ(a)=1 Y
i:ai=1
xiY
j:aj=0
(1 −xj),
he s anda d mul ilinea indica o expansion. Fo each sa is ying assignmen a, le Sa={i:
ai= 1}. Conside he o de -|Sa|pa ial de i a i e ∂xSaχφ. Mul ilinea i y gi es
∂xSaχφ=X
b:φ(b)=1, Sa⊆SbY
j /∈Sa(1 −xj)1−bj.
E alua ing a x= 0 (o p ojec ing o he cons an e m) isola es he e m o b=a, while
any b=aei he iola es Sa⊆Sbo con ibu es a ac o ha anishes a x= 0. Thus
he ow co esponding o (R=Sa, α = 1) has a unique 1in he column o he monomial
suppo ed on ∅and ze os in he same column o all Sbwi h b=a. Va ying ao e he k
sa is ying assignmen s yields a k×kiden i y subma ix inside he o de -ℓSPDP ma ix o
any ℓ≥1(since we can include he ows (R=Sa, α = 1) wi h |Sa| ≤ nand p ojec columns
app op ia ely as in §2.3). Hence kSPDP, ℓ(χφ)≥k≥2n/2.
Rema k 35.This a gumen is ield-independen and uses only mul ilinea i y and he indi-
ca o s uc u e. I aligns wi h he subma ix-embedding b idge o §2.3 and he uni o m
mono onici y o §2.6.
96

17.4 En opy/weigh no e (suppo o andom pa i ioning)
When an auxilia y “good pa i ion” o he a iables is equi ed (e.g., dis ibu ing a iables
among de i a i e/shi /ancho se s), a s anda d en opy bound su ices:
Lemma 96 (En opy/weigh bound, one-line o m).Le a andom pa i ion [n] = Y∪Z∪W
place each coo dina e independen ly in o Y, Z, W wi h p obabili y 1/3. Then
P h|Y|− n
3> εn o |Z|− n
3> εn o |W|− n
3> εn i≤2−Ω(ε2n).
In pa icula , wi h p obabili y 1−2−Ω(n)all h ee pa s ha e size Θ(n); a union bound o e
2O(n)candida e s uc u es s ill lea es 2−Ω(n) ailu e p obabili y.
Use. This gua an ees balanced pa ame e egimes in andom o pseudo andom decompo-
si ions used o place pocke s o o ensu e enough de i a i e/shi ows exis a he a ge
o de .
C oss- e e ences.
•Subma ix embedding and uni o m mono onici y: §2.3–§2.6.
•BP→SPDP P-side collapse ensu ing he uppe bound: §2.1.
•T ans e om classical ∂-ma ix bounds o SPDP: Co olla y 18 in §2.6.
Rema k 36 (In e p e i e Signi icance).The N-F ame o malism cla i ies long-s anding co -
espondences be ween analy ic, algeb aic, and geome ic me hods: hese appea as dis inc
p ojec ions o a single in o ma ional mani old ela i e o he obse e ’s bounda y condi ions.
The same bounded-ac ion cons ain ha limi s in e ence also yields p edic i e s uc u e—
exponen ial ha dness, spec al gaps, and cu a u e bounds—consis en wi h empi ical esul s
in complexi y heo y. In his sense he amewo k does no ende ma hema ics subjec i e;
i o malises he geome y o in e ence i sel , showing ha he laws o deduc ion possess an
in insic obse e -coupled s uc u e.
(The in e p e i e/philosophical syn hesis o me ly in §14.5 is consolida ed in §15 “In e p e i e
Syn hesis,” whe e i s ole is cla i ied ela i e o he o mal lowe bounds abo e.)
18 The 3-SAT “God Mo e”: om ha d ins ances o sep-
a a ion ( ull p oo s)
This sec ion u ns he lowe -bound machine y om §14 in o a language-le el sepa a ion.
We ix once and o all a cons an de i a i e o de ℓ∈ {2,3}(any ixed ℓ≥2wo ks
whe e e s a ed). Le Mℓ( )deno e he o de -ℓSPDP ma ix o a mul ilinea polynomial
( ows indexed by (R, α)wi h |R|=ℓand deg α≤ℓ; columns indexed by all mul ilinea
monomials), and le kSPDP,ℓ( ) := ank(Mℓ( )).
97
Th oughou , o a 3-CNF φon a iables x= (x1, . . . , xn), i s cha ac e is ic polynomial
is
χφ(x) = X
a∈{0,1}n:φ(a)=1 Y
i:ai=1
xiY
i:ai=0
(1 −xi),
which ag ees wi h 1SAT(φ)on {0,1}nand is mul ilinea .
18.1 Non-ci cula a chi ec u e
We use he explici 3-CNF amily {φn}n∈N om §14 (Ramanujan–Tsei in ou e). Sec ion 14
p o ed:
Theo em 97 ( ecalled, ha d amily).The e exis s ε > 0such ha
kSPDP,ℓ(χφn)≥2εn o all su icien ly la ge n.(9)
Independen ly, §2.1 (b anching-p og am compila ion) p o ed:
Theo em 98 ( ecalled, P-side uppe bound).I L∈P, hen o each inpu leng h n he
leng h-nslice Lnhas a mul ilinea ep esen a i e L,n wi h
kSPDP,ℓ( L,n)≤nc o some cons an c=c(L, ℓ).(10)
This pai o ac s su ices o he sepa a ion, once we check obus ness unde s anda d
paddings/encodings.
18.2 3-SAT as he ha d language
We wo k wi h he canonical NP-comple e language
3-SAT =φ:φis a 3-CNF and ∃a∈ {0,1} a s(φ)φ(a)=1.
Fo each n, le φnbe he explici ins ance om §14 and le χφnbe i s cha ac e is ic polyno-
mial.
Theo em 99 (Exponen ial SPDP ank on ha d 3-SAT ins ances).The e exis s ε > 0such
ha
kSPDP,ℓ(χφn)≥2εn o all la ge n.
P oo . This is exac ly (9), es ablished in §14 ia he Ramanujan–Tsei in cons uc ion and
he ans e om ∂-ma ix lowe bounds o SPDP ank (c . §2.3–§2.6).
Lemma 100 (SPDP ank unde p ojec ion and subma ices).Le be mul ilinea on a i-
ables spli as (x, y)wi h disjoin suppo s. I we dele e all SPDP columns whose monomials
use any y- a iable, he esul ing subma ix o Mℓ( )has ank ≤ kSPDP,ℓ( ).
P oo . Dele ing columns canno inc ease ank.
We’ll use his oge he wi h exac p oduc ac o iza ions ha a ise om benign paddings.
98
18.3 Two algeb aic ac s used o padding
We isola e wo ma ix-le el lemmas ha we will apply o padded o mulas.
Lemma 101 (P oduc wi h a dummy ac o ).Le (x)be mul ilinea on xand D(d)be any
mul ilinea polynomial on disjoin dummy a iables d, and ix ℓ≥0.
1. Fo e e y S⊆ a s(x)wi h |S|=ℓand e e y shi α(x)on x(no d- a iables),
α(x)·∂S (x)D(d)=α(x)·∂S (x)D(d).
2. Conside he block o Mℓ( ·D)whose columns a e es ic ed o monomials on xonly
(i.e., igno ing any column ha uses a d- a iable). Tha block equals Mℓ( )mul iplied
on he igh by a diagonal ma ix wi h he nonze o scala D(0,...,0) on i s diagonal
i we p ojec he dummy a iables o d= 0.
3. In pa icula , i Dis a nonze o mul ilinea polynomial (e.g., a nonze o cons an o a
single dummy a iable e alua ed a 1), hen he ank o ha block is ank(Mℓ( )).
P oo . I em 1 is he Leibniz ule oge he wi h he ac ha we ne e di e en ia e w. . .
a dummy; hence D ac o s ou . Fo i em 2, he columns indexed by monomials on xpick
exac ly he coe icien ec o s o α·∂S , scaled uni o mly by he ( ixed) coe icien s o Din
he dummy-only basis. E alua ing dummies a a ixed Boolean assignmen (e.g., d= 0 o
d= 1) makes ha ac o a nonze o scala i Ddoes no anish he e. I em 3 ollows.
Lemma 102 (Block-lowe - iangula sum).I a ma ix Mis block-lowe - iangula wi h
diagonal blocks B1, . . . , B , hen
ank(M)≥
X
i=1
ank(Bi).
P oo . The column space o Mcon ains he di ec sum o he column spaces o he diagonal
blocks ( ia he na u al embeddings), so ank is a leas he sum.
18.4 No-padding ( obus ness o s anda d dummy paddings)
We o malize he padding used in p ac ice: add esh dummy a iables ha appea only in
uni clauses, and ne e mix wi h o iginal a iables.
De ini ion 25 (Uni -dummy padding).Gi en a 3-CNF φ(x), de ine pad(φ)on (x, d)by
adding (a polynomial numbe o ) uni clauses dj o esh dummies d= (d1, . . . , d ), and do
no in oduce any clause ha mixes dwi h x. Then he sa is ying assignmen s o pad(φ)
a e p ecisely he pai s (a, 1)wi h a|=φand d=1.
Consequen ly, he cha ac e is ic polynomial ac o s as
χpad(φ)(x, d) = χφ(x)·
Y
j=1
dj.(11)
99
P oo o (11).A Boolean assignmen (x, d)sa is ies pad(φ)i x|=φand e e y uni clause
djis ue, i.e., d=1. In he in e pola ion sum de ining χpad(φ), he d-componen con ibu es
Qjdj.
Theo em 103 (No-padding unde uni -dummy padding).Fo uni -dummy paddings pad as
abo e,
kSPDP,ℓχpad(φ)≥ kSPDP,ℓ(χφ).
P oo . W i e χpad(φ)=χφ(x)·D(d)wi h D(d) = Qjdj. By Lemma 101(1), o e e y ow
index (S, α)on x- a iables we ha e
α·∂Sχpad(φ)=α·∂SχφD(d).
Res ic he SPDP columns o monomials in xonly (dele e all columns using any dj). By
Lemma 101(2)–(3) ha column- es ic ion is a nonze o scala mul iple o Mℓ(χφ), hence
has ank kSPDP,ℓ(χφ). By Lemma 100, dele ing columns ne e inc eases ank, so he ull
ankMℓ(χpad(φ))is a leas ha la ge.
Co olla y 104 (Robus ness o he lowe bound).I kSPDP,ℓ(χφn)≥2εn hen
kSPDP,ℓχpad(φn)≥2εn o any uni -dummy padding.
18.5 Round- ip padding equi alence (sa e NC0augmen a ion)
We may also use an NC0“ ound- ip” padding ha helps manage o e laps bu p ese es
sa is iabili y and ank up o poly ac o s.
Theo em 105 (Round- ip NC0padding).The e exis NC0maps
pad : 3CNF(n)→3CNF(n+O(nlog n)),unpad : 3CNF(n+O(nlog n)) →3CNF(n),
such ha o e e y φ:
1. (Sa is iabili y p ese a ion) φis sa is iable i pad(φ)is sa is iable.
2. (Assignmen eco e y) Any sa is ying assignmen o pad(φ)maps (in NC0) o a
sa is ying assignmen o φ.
3. (Rank p ese a ion) kSPDP,ℓχpad(φ)≥ kSPDP,ℓ(χφ)/poly(|φ|).
4. (Independence) The dummy a iables in pad(φ)do no appea oge he wi h o iginal
a iables in any clause beyond i ial uni clauses, so he SPDP ma ix acqui es a
block-lowe - iangula s uc u e.
P oo . S anda d NC0gadge s can dis ibu e clause load on o esh dummies (in oducing
only uni clauses o he new a iables) while p ese ing sa is iabili y and enabling di ec NC0
decoding— his gi es (1)–(2). The polynomial ank p ese a ion (3) ollows by combining
(11) wi h Lemma 102: he padded cha ac e is ic polynomial is a p oduc o he o iginal wi h
a dummy ac o , and he SPDP ma ix o e a sui able ow/column o de is block-lowe -
iangula wi h he o iginal block on he diagonal; he diagonal block’s ank con ibu es
addi i ely, and mul iplica i e dummy ac o s canno cancel i (Lemma 101). Hence ank
deg ades by a mos a polynomial (indeed, i o en s ays he same). P ope y (4) is enginee ed
by cons uc ion.
100
18.6 Sepa a ion
We now s a e he logical consequence.
Theo em 106 (Sepa a ion on 3-SAT).3-SAT /∈P. In pa icula , P= NP.
P oo . Suppose 3-SAT ∈P. Then by he P-side uppe bound (10), o each inpu leng h
N he leng h-Nslice has o de -ℓSPDP ank ≤Nc. Apply his o he explici ins ances φn
(o o hei innocuous paddings om §15.4–§15.5): we would ge kSPDP,ℓ(χφn)≤poly(n).
This con adic s Theo em 99, which gi es kSPDP,ℓ(χφn)≥2εn. Hence 3-SAT /∈P. Since
3-SAT ∈NP, we conclude P= NP.
Rema k 37 (The “God Mo e”).The de e minis ic cons uc ion o a wi ness w∈V⊥
nin §2.7
is he algeb aic “obse e dualiza ion”: a single wannihila es he en i e compiled P-side span
ye pai s non i ially wi h he explici ha d polynomials χφn. In his sense, he sepa a ion
is ealized by a single linea unc ional ha “sees” beyond he polynomial- ime subspace.
Wha was c ucial.
1. Ha d lowe bound (§14 →Theo em 99): explici {φn}wi h kSPDP,ℓ(χφn)≥2εn.
2. P-side uppe bound (§2.1 →(10)): e e y L∈Phas kSPDP,ℓ( L,n)≤nc.
3. Robus ness (§15.4–§15.5): uni -dummy/NC0paddings do no educe SPDP ank
below he o iginal up o polynomial ac o s (Lemmas 101–102).
Toge he hey yield he sepa a ion.
19 CNF-SAT as an Al e na i e Ha d Language (Ze o-
Tes Cons uc ion)
This sec ion gi es a sel -con ained, algeb aic ha d amily based on he s anda d CNF-SAT
encoding. I is independen o he expande /Tsei in ou e and uses only a ze o- es polyno-
mial oge he wi h a clean monomial-independence a gumen o ob ain exponen ial SPDP
ank. (We p esen he lowe bound o he global SPDP ma ix—i.e., allowing all de i a-
i e o de s. This sec ion is supplemen a y and no needed o he ixed-o de ℓ∈ {2,3}
sepa a ion used elsewhe e.)
19.1 CNF →polynomial: he ze o– es
Le Φnbe a 3-CNF on a iables x1, . . . , xnwi h clauses C1, . . . , Cm. Each clause Cjis he
disjunc ion o h ee li e als ℓj,1, ℓj,2, ℓj,3, whe e a posi i e li e al is ℓ=xiand a nega i e
li e al is ℓ= 1 −xi.
De ini ion 26 (CNF ze o– es polynomial).Se he clause sum
Sj(x) := ℓj,1(x) + ℓj,2(x) + ℓj,3(x),
101

and he CNF polynomial
Pn(x) :=
m
Y
j=1
Sj(x).
Theo em 107 (Polynomial decides SAT).Fo e e y assignmen a∈ {0,1}n,
a|= Φn⇐⇒ Pn(a)= 0.
P oo . I a alsi ies some clause Cj, hen each li e al in Cje alua es o 0, hence Sj(a)=0,
and hus Pn(a) = 0. Con e sely, i asa is ies e e y clause, hen o each ja leas one li e al
in Cje alua es o 1, hence Sj(a)≥1, so he p oduc is nonze o.
Thus he language
CNF-Ha dn:= a∈ {0,1}n:Pn(a)= 0 
is exac ly SAT(Φn).
19.2 Combina o ics o monomials and linea independence
W i e he p oduc in “choice o m” by selec ing one li e al om each clause.
Theo em 108 (Numbe o monomials).Expanding Pnyields exac ly 3mmul ilinea mono-
mials:
Pn(x) = X
s∈{1,2,3}m
m
Y
j=1
ℓj,sj(x).
Each choice s ing s= (s1, . . . , sm)picks one li e al om each clause and de e mines a
dis inc monomial.
P oo . Di ec expansion o he p oduc o sums; dis inc choice s ings yield dis inc se s o
li e als and hence dis inc mul ilinea monomials.
We nex show hese 3mmonomials a e linea ly independen as unc ions o e {0,1}n,
which al eady en o ces a la ge ank o any coe icien -based o coe icien - eco e ing ma ix.
Lemma 109 (Selec o assignmen s ⇒independence).Assume he base ield has cha ac e -
is ic 0o a p ime >3. Then he 3mmonomials
Ms(x) :=
m
Y
j=1
ℓj,sj(x)s∈ {1,2,3}m
a e linea ly independen .
P oo . Fo each s∈ {1,2,3}mcons uc a selec o assignmen a(s)∈ {0,1}nas ollows: o
each clause j,
•se he unde lying a iable o make he chosen li e al ℓj,sjequal o 1,
102
•and se he same a iable (i i eappea s) so ha e e y o he li e al in ha clause
e alua es o 0.
(I a a iable appea s in mul iple clauses, pe o m he assignmen s clause-by-clause; since
each li e al is ei he xio 1−xi, o each clause we can always ealize ℓj,sj= 1 while o cing
he o he wo o 0; con lic s ac oss clauses do no a ise in he e alua ion o Ms s. o he
monomials because a monomial includes exac ly one li e al pe clause.)
Unde a(s),
Msa(s)= 1,
M a(s)= 0 o all =s,
since any =sdisag ees in a leas one clause jwhe e ℓj, jhas been se o 0. Thus he
3me alua ion ec o s Msa( ) s o m he iden i y ma ix, p o ing linea independence.
(The cha ac e is ic condi ion ules ou acciden al cancella ions o he cons an s {0,1}.)
19.3 Exponen ial SPDP ank (global)
Le MSPDP(Pn)deno e he global SPDP ma ix o Pn( ow-conca ena ing he coe icien ec-
o s o α·∂|R|
xRPno e all (R, α)). As shown in §2.3, he classical pa ial-de i a i e coe icien
ma ices PDS,T (Pn)appea (up o anspose) as li e al subma ices o MSPDP(Pn). In pa -
icula , by choosing Sclause-by-clause and aking α= 1, one ob ains a block in which he
columns a e indexed by he monomials {Ms}and he ows pick hei coe icien s. Lemma 109
implies ha block has ull column ank 3m.
Co olla y 110 (Global SPDP ank is exponen ial).O e any ield o cha ac e is ic 0o
>3,
kSPDP,all(Pn)≥3m= 2Ω(n) o m= Θ(n).
P oo . By Lemma 109, he 3mmonomials in Pna e linea ly independen ; he co esponding
pa ial-de i a i e coe icien ma ix has ank 3m. By he subma ix embedding (§2.3), i s
ank is bounded abo e by he global SPDP ank o Pn. Hence k MSPDP(Pn)≥3m. Fo
m= Θ(n),3m= 2Ω(n).
Rema k 38.This lowe bound is o he global SPDP ank (all de i a i e o de s). Ou main
ixed-o de lowe bounds ( o ℓ∈ {2,3}) a e supplied by he Tsei in/expande ou e; he
p esen sec ion se es as an independen algeb aic wi ness ha he phenomenon is obus .
19.4 Ha d language ia ze o es
De ini ion 27 (CNF-Ha d language).
CNF-Ha dn:= a∈ {0,1}n:Pn(a)= 0 = SAT(Φn).
Then CNF-Ha d := SnCNF-Ha dnis in NP (wi ness: a sa is ying assignmen ), and by
Co olla y 110 he associa ed polynomial amily {Pn}has exponen ial global SPDP ank
whene e m= Θ(n).
103
19.5 Pu pose and placemen
Pu pose. This sec ion p o ides a second, pu ely algeb aic ha d amily (dis inc om he
#3SAT cha ac e is ic polynomial and he expande /Tsei in ou e), showing ha exponen ial
SPDP ank a ises al eady om he simple clause-sum p oduc encoding o SAT.
20 Fo mal Comple ion o he “God Mo e”
This sec ion closes he sepa a ion by combining a uni o m codimension collapse o all
polynomial- ime compu a ions wi h a ma ching exponen ial lowe bound o NP wi nesses
unde he same es ic ion, and hen packaging he algeb aic ank in o a seman ic wid h
measu e (CEW). Th oughou we wo k o e a ield o cha ac e is ic 0o su icien ly la ge
p ime; all polynomials a e mul ilinea ized as usual (which p ese es he SPDP ank bounds
we use).
20.1 Uni o m codimension collapse o all P
Le Mbe a de e minis ic Tu ing machine unning in ime (n) = nk. Le con Poly(M, n)
deno e he Cook–Le in ableau polynomial PM,n om Theo em 64, encoding all alid leng h-
naccep ing ableaux o M; i has cons an deg ee and N= poly(n) a iables.
We apply a single, leng h-O(log n)explici es ic ion ρ⋆(cons uc ed ia an expande /PRG
+ de e minis ic swi ching-lemma enume a ion) ha ixes a cons an ac ion o a iables uni-
o mly o all such M.
Theo em 111 (Codimension collapse; de e minis ic).Fo e e y k he e is a compu able
map n7→ s⋆(n)∈ {0,1}O(log n)such ha he es ic ion ρ⋆:= ρs⋆(n)sa is ies, o e e y
de e minis ic M unning in ime nk,
kSPDP,ℓcon Poly(M, n)↾ρ⋆≤n6 o each ixed ℓ∈ {2,3}.
comple e, wi h s anda d ing edien s. 1. Wid h-5 embedding. By he compila ion in
§2.1, a ime-nkcompu a ion yields a laye ed BP o leng h L′=nO(k)and wid h W=
poly(n). The Cook–Le in ableau polynomial PM,n om Theo em 64 gi es a cons an -
deg ee polynomial wi h N= poly(n) a iables whose accep ing se coincides wi h M’s
language on {0,1}n. Ba ing on-s yle un olling o local cons ain s yields an equi alen
bounded-wid h o mula.
2. De e minis ic swi ching es ic ion. Use a de andomized Aj ai–Wigde son/Hås ad
scheme: a cons an -p ac ion o a iables is ixed by ρ⋆while gua an eeing ha e e y
DNF/CNF o wid h ≤5and size ≤n3collapses o decision- ee dep h ≤clog n. The
seed is chosen de e minis ically by enume a ing 2O(log n)= poly(n)seeds and es ing
he wid h–dep h p edica e ( he es i sel is polynomial o he bounded-wid h amily).
Thus ρ⋆is explici and uni o m in n.
3. Bound he su i ing monomials. A e applying ρ⋆, each bounded-wid h sub o -
mula in he ableau cons ain s collapses o decision- ee dep h O(log n); hence he
104
numbe o esul ing monomials is a mos nO(1) (a s anda d “dep h →lea es →mono-
mials” a gumen ). Conc e ely we ob ain #monomials ≤n4.
4. SPDP ank bound. Fo ixed o de ℓ∈ {2,3}, he ℓ-shi ed pa ial-de i a i e ma ix
has a mos #monomials ×nO(1) nonze o columns/ ows, hence ank ≤n6a e a
ha mless padding o cons an s. This yields he s a ed bound o e e y Mand comple es
he p oo .
20.2 A ma ching NP lowe bound unde he same es ic ion
Theo em 112 (Uni o m NP-side ank lowe bound).Le Vbe any polynomial- ime e i ie
o a language L∈NP, and le {px}be he compiled wo kloads p oduced by he de e minis ic
adius-1compile (in he diagonal basis wi h Π+=A) on inpu s xo leng h n. The e
exis absolu e cons an s c0, c1>0and a canonically de ined es ic ion ρ⋆( he uni e sal
es ic ion) such ha , o all su icien ly la ge n,
Γk,ℓpx↾ρ⋆≥nc0log n o some xwi h |x|=n, and wi h k, ℓ =c1log n.
In pa icula , he NP-side SPDP ank is supe -polynomial unde he same (k, ℓ)used on he
P-side.
P oo . S ep 1: Uni o m educ ion o a s uc u ed CNF amily. By Cook–Le in, o each inpu
x he e is a CNF Φxo size poly(n)such ha Φxis sa is iable i x∈L. Using he ins ance-
uni o m compile ’s layou , we e ine he educ ion so ha Φxis block-s uc u ed: a iables
pa i ion in o cons an - adius blocks; each clause ouches a mos a cons an numbe o
blocks ( adius-1 locali y). This is s anda d: simula e V’s ime-poly(n)compu a ion wi h
local wi ing gadge s and clause empla es con ined o adius-1neighbo hoods. (All empla es
a e independen o x; only hei ac i a ions and li e als depend on x.)
S ep 2: Expande augmen a ion and p i a e li e als. Le Gnbe a ixed amily o d- egula
expande s on N= Θ(n)clause-blocks wi h edge expansion α > 0. A ach o Φxa Tsei in-
s yle pa i y sca old: each clause-block ecei es an inciden pa i y cons ain ia edges o
Gn. Fo e e y clause occu ence we add a p i a e li e al ( esh a iable) so ha , unde
es ic ion, each clause-block e ains an inciden li e edge wi h high deg ee o independence.
This yields a CNF b
Φxo size poly(n)whose s uc u e (blocks, incidence) is uni o m in nand
independen o x, while he ac i a ion pa e n depends on x.
S ep 3: Uni e sal es ic ion ρ⋆.De ine ρ⋆by de e minis ically ixing all non-inciden
auxilia ies and non-in e ace a iables so as o: (i) p ese e one inciden pa i y edge pe
block, (ii) elimina e clause o e laps beyond adius-1, (iii) keep exac ly one p i a e li e al pe
clause-block ali e. Because he compile is adius-1and he empla e lib a y is ini e, ρ⋆is
compu able uni o mly in nand independen o x. Pos - es ic ion, e e y block exposes a
cons an -size in e ace whose li e coo dina es a e he p i a e li e al and i s a ached pa i y
bi .
S ep 4: Keys/incidence p ese a ion. Le keys(·)deno e he se o li e coo dina es ( a i-
ables/pa ials) used by SPDP ows. We claim:
keys
b
Φx↾ρ⋆={one li e inciden pe block}∪{i s p i a e li e al}.
105
Lemma 118 (PRG o wid h-5 o mulas).The e exis cons an s c1, c2>0and an explici
gene a o G:{0,1}c1log n→ {0,1}Nsuch ha he induced es ic ions ρs(wi h s a a e
p=1
40)ε- ool e e y Boolean o mula o wid h ≤5and size ≤nc2wi h ε≤n−4. Consequen ly,
enume a ing all s∈ {0,1}c1log nyields a uni e sal s∗whose ρs∗sa is ies he dep h bound o
Theo em 117 simul aneously o all o mulas in he amily.
P oo . Cons uc Gas an expande -walk gene a o on a cons an -deg ee (nO(1), λ)-expande
wi h λ < 1 ixed; ead o bi s along O(log n)s eps om a ixed s a , g ouped in o blocks
pe o mula-coo dina e. S anda d Che no - ype and mixing bounds gi e pai wise/limi ed
independence su icien o ool wid h-5, size-nc2 o mulas wi h e o ε≤n−4(de ails: he
accep ance p obabili y di e ence is bounded by he spec al ail λL, wi h L= Θ(log n)).
Thus a union bound o e ≤nc2 o mulas ensu es exis ence o a single good seed; enume a ion
o e {0,1}c1log n inds i .
20.7.3 Tableau- o-wid h-5 ansla ion ( ull p oo )
Claim 119 (Tableau as wid h-5 DNF).The accep ing- ableau p edica e o a ime- (n) = nk
TM on leng h ninpu s can be exp essed as a DNF o wid h ≤5and size nO(1).
P oo . The Cook–Le in cons ain s a e deg ee-≤3local checks ying (τ, i) o (τ+ 1, i′)
h ough he ansi ion unc ion. Each local cons ain in ol es a mos 3 cell/ ime a iables
plus (a mos ) 2 auxilia y indica o a iables o s a e/head ( he single-head and single-s a e
axioms). Hence each local clause is a conjunc ion o ≤5li e als. The accep ing p edica e is
he conjunc ion (o e all τ, i) o hese cons an -wid h clauses oge he wi h a inal accep ing-
s a e li e al. Dis ibu e he conjunc ion in o DNF by un olling: each e m selec s one li e al
pe clause (o i s o ced complemen ), hence wid h ≤5. The numbe o clauses is polynomial
in n(speci ically O( (n)·nk) = nO(k)), so he DNF size is nO(1). This compile o malizes he
in a ian disco e ed empi ically by he e olu iona y algo i hm (EA; Appendix H), ensu ing
adius-1 window isola ion and p ese ing he bounded- enso -p oduc s uc u e ha yields
polynomial SPDP ank.
20.7.4 Uni o m collapse (consequence)
Combining §17.7.1–17.7.3, he es ic ion ρ⋆:= ρs∗ob ained by enume a ing s∈ {0,1}O(log n)
simul aneously collapses e e y bounded-wid h o mula appea ing in con Poly(M, n)( o any
ime-nkTM M) o decision- ee dep h O(log n). Lemma 116 hen yields he n6SPDP- ank
bound.
Rema k 42 (usage).This subsec ion is used o jus i y ha a single explici es ic ion ρ⋆
wo ks o all P-side ableau polynomials a a ixed inpu leng h n. The sepa a ion needs
p ecisely his uni o mi y.
20.8 SPDP Res ic ion Lemma (Kayal–Saha– ype wi ness) — ull
p oo
Lemma 120 (NP Exponen ial Lowe Bound).Fix ℓ∈ {2,3}and he uni e sal ρ⋆ om
§17.7.4. Le Vbe any polynomial- ime e i ie o inpu s o leng h nwi h wi ness leng h
112

m= poly(n), and le
J(x, w) := join Poly(V, n)
be he mul ilinea polynomial encoding he accep ing ableaux o Von inpu x∈ {0,1}nand
wi ness w∈ {0,1}m. Then he e exis s a wi ness wsuch ha
kSPDP,ℓJ↾ρ⋆[w]= 2Ω(n).
P oo . P elimina ies and no a ion. Le Xbe he se o inpu a iables and W he se
o wi ness a iables. A e mul ilinea iza ion, Jis mul ilinea in X∪W. Apply ρ⋆ o he
X∪W a iables; by cons uc ion ρ⋆ ixes a leas a cons an ac ion and lea es a mos
p=1
40 ac ion s a ed. Le U⊆X∪Wbe he se o a iables le s a ed by ρ⋆, and w i e
J⋆:= J↾ρ⋆as a mul ilinea polynomial in he s a ed a iables U(a subse o he o iginal
a iables).
S ep 1 (Va iable spli ing). Fo each inpu a iable xi∈X ha appea s in mo e han
∆cons ain - ac o s ( o ∆ := clog n o a su icien ly la ge uni e sal cons an c), eplace i s
appea ances by esh a iables xi,1, . . . , xi, iand add equali y wi es by in oducing a spli e
gadge ha en o ces xi=xi,1=··· =xi, iusing deg ee-≤3cons ain s; equi alen ly (and
mo e simply o ou ank a gumen ), eplace each appea ance o xiby xizi,j wi h esh zi,j
used exac ly once (a s anda d “deg ee-1 pe a iable” linea iza ion), and include a balancing
ac o o ensu e he accep ing se is p ese ed. The e ec is: e e y li e al ha appea s in
Jappea s a mos once pe a iable ins ance, and each ins ance is indi idually add essable.
Le he esul ing polynomial be ˜
J. Because he gadge is local and deg ee-≤3,˜
J emains
mul ilinea and he e i ie beha io is unchanged unde he na u al p ojec ion. The o al
numbe o a iables inc eases by a mos a polylog ac o ; we abso b his in o cons an s.
S ep 2 (Disjoin neighbo hoods o local accep ance pa e ns). The join ableau
encodes T=nO(1) ime s eps. The e exis βn disjoin , cons an - adius neighbo hoods
N1, . . . , Nβn in he space- ime g id ( o some ixed β > 0) such ha , condi ioned on ixed
bounda y da a ou side SjNj, each Njsuppo s a leas wo locally accep ing pa e ns ha
a e mu ually exclusi e (e.g., wi ness-con olled b anches ha o ce accep s. ejec locally
a ha window). This is s anda d: a polynomial- ime e i ie can consul disjoin blocks o
he wi ness o o ce local accep ing ce i ica es; by padding ime and using non-o e lapping
ape in e als, we can ensu e disjoin ness.
Le S⊆[βn]be any index se o size K:= ⌊βn⌋. Fo each j∈S, ix wo al e na i e local
pa e ns π(0)
j, π(1)
jon Nj, each ealized by a conjunc ion o ≤c0 esh indica o a iables (pos -
spli ) and a mos c0wi ness a iables, wi h c0an absolu e cons an . Because neighbo hoods
a e disjoin , hese pa e ns in ol e disjoin a iable se s ac oss di e en j.
S ep 3 (Res ic ion and wi nessing). Apply ρ⋆. Because ρ⋆lea es a p- ac ion o
a iables s a ed independen ly o V, and neighbo hoods a e disjoin , a leas a γ > 0 ac ion
o he neighbo hoods e ain all hei pa e n a iables s a ed (Che no bound). Fix S o be
any subse o indices o which all pa e n a iables emain s a ed (o size s ill Θ(n)a.a.s.;
de e minis ically, choose he i s K′:= ⌊γβn⌋such neighbo hoods in a canonical o de ing —
since we a e p o ing exis ence o a gi en n, we may ix any such S ha occu s o in ini ely
many n; he ini ely many excep ional ncan be ha d-coded).
De ine he wi ness was ollows: o each j∈S, se he wi ness bi s ha selec pa e n π(bj)
j
wi h bj∈ {0,1}; o j /∈S, se wi ness bi s a bi a ily (e.g., 0). Because neighbo hoods a e
113
disjoin and he ableau cons ain s a e local, each choice ec o b= (bj)j∈S∈ {0,1}K′yields
a dis inc accep ing local con igu a ion on U∩Sj∈SNj. In he polynomial ˜
J⋆[w] := ˜
J↾ρ⋆[w],
each binduces a unique monomial Mbconsis ing exac ly o he s a ed indica o a iables
o he chosen pa e ns {π(bj)
j:j∈S}(mul ilinea i y and disjoin ness ensu e uniqueness and
no cancella ions o e cha ac e is ic 0o la ge p ime).
S ep 4 (ℓ-SPDP iden i y mino ). Conside he ℓ-shi ed pa ial-de i a i e ma ix
SPDPℓ(˜
J⋆[w] ). Index i s columns by he monomials {Mb}b∈{0,1}K′(a subse o all columns)
and index i s ows by he se o de i a i e ope a o s ob ained by di e en ia ing w. . . he
(disjoin ) pa e n-selec o s o each j∈S, one a iable pe neighbo hood, and hen mul i-
plying by he co esponding a iable ( he s anda d “de i a i e-shi ” choice ha isola es one
e m pe neighbo hood). Because neighbo hoods a e disjoin , hese ows ac independen ly
ac oss neighbo hoods; he e alua ion o ow b′on column bis 1i b=b′and 0o he wise
(each de i a i e/shi kills all monomials excep he one ha exac ly ma ches he chosen
pa e n ec o ). The e o e he subma ix on ows/columns indexed by {b}is he iden i y
ma ix o size 2K′.
Hence k(SPDPℓ(˜
J⋆[w])) ≥2K′= 2Ω(n). The same lowe bound holds o J⋆[w](spli
a iables can be me ged by a ank-noninc easing p ojec ion). This p o es he lemma.
Rema k 43 (usage).This lemma is used in he main p oo ( he NP-side exponen ial lowe
bound in §17.2 / Theo em 111). The explici “design-mino ” cons uc ion abo e is he ull
a gumen ; no ex e nal o maliza ion is equi ed.
20.9 Uni o m SPDP es ic ion o NP (explici cons an s; ull p oo )
This subsec ion eco ds a uni o m-pa ame e s eng hening. I is no equi ed o he sepa-
a ion, bu some eade s may app ecia e explici scales.
Lemma 121 (Uni o m NP es ic ion wi h explici g ow h).Le Vbe any ime-nk e i ie
and n≥16. Le ρs⋆(n)be he uni e sal es ic ion om §17.7.4 wi h seed leng h O(log n).
The e exis s a wi ness w⋆(n)o leng h m= Θ(nlog n)such ha , o ℓ= 3 and any k′=
⌈αlog n⌉wi h α≤1
2,
kSPDP,ℓjoin Poly(V, n)↾ρs⋆(n)[w⋆(n)]≥21
4nlog n.
P oo . Apply he spli - a iable gadge o §17.8 o li he inpu a iable se om n o
N:= n+nlog n= Θ(nlog n)indica o s wi h pe - a iable deg ee 1. The uni e sal e-
s ic ion ρs⋆(n)lea es a cons an ac ion o a iables s a ed. Selec a canonical se So 1
2N
s a ed “p ima y” indica o s; by he same local-pa e n design as in §17.8 bu now o ganized
in Θ(N)disjoin neighbo hoods, choose w⋆(n) o ealize one o wo pa e ns pe neighbo -
hood. Exac ly as be o e, he ℓ-SPDP ma ix on he sub amily o columns indexed by hose
2|S|choices con ains an iden i y mino o size 2|S|. Taking |S|=1
2N= Θ(nlog n)and ese -
ing a cons an ac o o co e o e laps and bounda y e ec s yields he s a ed lowe bound
21
4nlog n. The de i a i e-o de pa ame e k′=⌈αlog n⌉only a ec s he size o he ope a o
index se ( ows), which emains polynomially bounded ela i e o he exponen ial numbe
o columns. Rank is ield-independen o mul ilinea indica o ma ices o e cha ac e is ic
0o su icien ly la ge p imes, so he bound holds o e Q.
114
Rema k 44 (usage).This lemma is supplemen a y. The sepa a ion only needs he exponen ial
NP lowe bound 2Ω(n)unde he same ρ⋆. The explici Θ(nlog n)-scale and cons an 1
4
exponen a e p o ided o eade s who p e e quan i ied g ow h.
Closing ema ks o §17.6–§17.9. Wha is essen ial o he main p oo ?
•§17.6 (Codimension Collapse) essen ial — i p o ides he P-side ank uppe bound
unde he uni o m ρ⋆.
•§17.7 (De e minis ic swi ching & uni e sal es ic ion) essen ial — i supplies he single
explici ρ⋆(seed O(log n)) ha wo ks o all P- ableaux.
•§17.8 (SPDP Res ic ion Lemma o NP) essen ial — i gi es he NP-side exponen ial
lowe bound unde he same ρ⋆.
Wha is op ional?
•§17.9 (Uni o m NP es ic ion wi h explici cons an s) op ional/supplemen a y — s eng h-
ens scales and cons an s; no equi ed o he P =NP sepa a ion.
20.10 Cons uc i e Ve i iabili y o SPDP Rank
This subsec ion closes he loop on cons uc i i y: he SPDP– ank p edica es we use a e e i-
cien ly checkable. We gi e (i) an A hu –Me lin p o ocol ha places SPDP– ank e i ica ion
in AM ⊆NP/poly, and (ii) a de e minis ic low– ank decision p ocedu e in he compiled/ e-
s ic ed se ing unde he same mild “column–applica ion” assump ion al eady used in ou
BP→SPDP pipeline.
Theo em 122 (SPDP– ank is AM– e i iable).Fix a de i a i e o de ℓ≥0. Le
L ank := {(p, ) : kSPDP,ℓ(p)≥ }.
Then L ank ∈AM.
P o ocol (A hu –Me lin). Wo k o e a p ime ield Fqwi h q > 2n.
1. A hu ’s challenge. Pick α∈Fm
quni o mly a andom (he e mequals he numbe
o dis inc a iables used o e alua e he SPDP en ies—i.e., enough coo dina es o
e alua e all monomials/de i a i es ha occu in he o de -ℓSPDP ma ix). Send α o
Me lin.
2. Me lin’s message. Re u n he indices o ows o he o de -ℓSPDP ma ix Mℓ(p)
o p, oge he wi h hei e alua ions a α:
1(α), . . . , (α)∈FC
q,
whe e Cis he numbe o columns o Mℓ(p).
115
3. A hu ’s e i ica ion (polynomial ime).
•Row ecompu a ion. Recompu e he same SPDP ows o pa α(each en y is a
ixed linea combina ion o e alua ions o pand i s ≤ℓ-o de pa ials a α, so his
cos s poly(n, ℓ) ield ope a ions pe en y). Check equali y wi h he submi ed
i(α).
•Independence es . Run Gaussian elimina ion on { i(α)}
i=1 o es linea inde-
pendence in O( 3) ield ope a ions.
Co ec ness.
•Comple eness. I k Mℓ(p)≥ , Me lin can choose linea ly independen ows o e
Fq(x). View each ow as a ec o o polynomials; a e subs i u ion x7→ α, hese
ec o s emain independen o e Fqwi h p obabili y 1 o gene ic αand, o e a ini e
ield, wi h p obabili y a leas 1−
qby he Schwa z–Zippel–DeMillo–Lip on lemma
applied o he de e minan o he × G am mino . Since q > 2nand ≤C≤2poly(n),
he ailu e p obabili y is <2−n.
•Soundness. I k Mℓ(p)< , hen e e y - uple o ows is dependen symbolically;
i.e., he e is a nonze o linea ela ion wi h polynomial coe icien s ha annihila es he
uple. E alua ing a andom α∈Fm
qyields he ze o ela ion wi h p obabili y a leas
1−
q≥1−2−n. Thus a chea ing Me lin is de ec ed wi h p obabili y ≥1−2−n.
•Running ime. Row ecompu a ion is poly(n, ℓ)pe en y ( ixed ℓ), so o al e i ica-
ion ime is polynomial; he independence es is O( 3).
Co olla y 123 (Rank ce i ica es o Ci cui –SAT).In ou sepa a ion, he NP wi nesses in-
duce explici SPDP ows/indices (unde he uni e sal es ic ion), so Ci cui –SAT ins ances
admi polynomial-size ank ce i ica es e i iable in polynomial ime (equi alen ly, in AM,
hence in NP/poly).
Theo em 124 (De e minis ic low- ank decision unde a column–o acle).Fix ℓ≥0. Le
Mℓ(p)be he o de -ℓSPDP ma ix o a mul ilinea p. Suppose we a e gi en a column-
applica ion o acle ha , on inpu a Boolean assignmen x∈ {0,1}n, e u ns
z(x) := V χ(x)∈F
in ime poly(n, ), whe e Mℓ(p) = U V is a (p omised) ank ac o iza ion o e F,χ(x)is
he monomial-e alua ion ec o , and is an a-p io i uppe bound on he ank (e.g., ≤n6
o he compiled classes unde ou uni e sal es ic ion). Then he e is a de e minis ic
polynomial- ime algo i hm ha decides whe he k Mℓ(p)≤ .
P oo . We un a black-box ank algo i hm (e.g., S o johann–Wiedemann) on Mℓ(p)using
only ma ix– ec o p oduc s wi h Mℓ(p)and Mℓ(p)⊤. These p oduc s educe o:
y7→ Mℓ(p)yand x7→ Mℓ(p)⊤x.
Because Mℓ(p) = U V , we can ealize hese as:
116
•y7→ U(V y), whe e V y is a linea combina ion o columns o V; since each column
co esponds o χ(x) o some de i a i e/shi pa e n (as in §2.3), we can e alua e V y
by ba ching he column-o acle on he necessa y χ(·)and linea ly combining.
•x7→ V⊤(U⊤x), symme ically.
The de i a i e/shi s uc u e needed o index columns is ully explici om he SPDP
cons uc ion (BP→SPDP compila ion); hus he ex ac o ha maps y( espec i ely x) o
he lis o χ(·)que ies is ixed and compu able in poly(n, ℓ, ) ime.
S o johann–Wiedemann compu es he ank wi h a numbe o black-box mul iplica ions
polynomial in (and loga i hmic in he ma ix dimension), so he o al unning ime is
poly(n, ). Hence deciding k Mℓ(p)≤ is de e minis ic polynomial ime unde he s a ed
column-o acle.
Rema k 45 (usage).S a us in he main p oo . This subsec ion is supplemen a y: he
AM p o ocol (Theo em 122) and he de e minis ic low- ank decision unde a column-o acle
(Theo em 124) a e no equi ed o p o e he sepa a ion in §§ 17.1–17.4 (collapse o P,
exponen ial esis ance o NP unde he same es ic ion, annihila o , and CEW w appe ).
Pu pose. They p o ide cons uc i e closu e: e e y SPDP- ank asse ion used in he
p oo can be e i ied e icien ly—AM in gene al, and de e minis ically in polynomial ime
o he compiled/ es ic ed ins ances whe e a column-applica ion o acle is al eady a ailable
om he BP→SPDP compila ion.
20.11 Ve i ie No maliza ion and Ins ance-Uni o m Ex ac ion
Building on he de e minis ic compila ion amewo k, we cons uc an ins umen ed machine
M′ ha p epends a s a ic clause-gadge shee and o ces a e i ie slice in e e y compiled
polynomial. This ensu es ha he NP- e i ica ion s uc u e is p ese ed h ough compila ion
while main aining polynomial SPDP ank bounds o P-side compu a ions.
Theo em 125 (Machine-Exac Compile Spec wi h Ve i ie No maliza ion).Fo e e y uni-
o m polynomial- ime decide Mo 3SAT ( unning in ime nc), he e exis s a de e minis ic
compile ha p oduces an ins umen ed machine M′wi h he ollowing p ope ies:
1. Clause-gadge p epending. The compiled polynomial PM′,n decomposes as
PM′,n(u, ) = QΦ(u) + RM′,Φ( ),
whe e u ep esen s clause a iables, ep esen s compu a ion a iables, QΦ(u)=1−
PC∈ΦVC(u)2encodes he CNF o mula as a sum-o -squa es o clause iola ions, and
RM′,Φ( )encodes he Tu ing machine ableau.
2. Locali y p ese a ion. Each clause gadge VCuses only adius-1(adjacen -cell) in-
e ac ions, main aining CEW(QΦ) = O(1).
3. Rank inhe i ance. The SPDP subma ix induced by he u-blocks sa is ies
Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n)≤nO(1),
o k, ℓ = Θ(log n).
117

4. Accep ance equi alence. Fo all inpu s x,M′accep s xi and only i Maccep s x.
P oo . By cons uc ion he compile p epends O(m)disjoin adius-1 clause gadge s p oduc-
ing QΦ(u) = 1 −PC∈ΦVC(u)2, and keeps he compu a ion ableau RM′,Φ( )sepa a e, hence
PM′,n(u, ) = QΦ(u) + RM′,Φ( )(I em 1).
Locali y (I em 2) ollows because each VC ouches O(1) adjacen cells ( adius-1). Fo I em
3, apply he ank mono onici y/in a iance ac s: p ojec ion o he u-blocks and es ic ion
o a iables a e ank non-inc easing (Lemma 16 and Lemma 17), and block-diagonal basis
changes p ese e ank (Lemma 19). Thus Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n). The P-side uppe bound
Γk,ℓ(PM′,n)≤nO(1) holds by he Wid h⇒Rank heo em a k, ℓ = Θ(log n)(Theo em 15).
I em 4 (accep ance equi alence) is immedia e om he s anda d TM ableau seman ics: he
added clause shee is independen o he compu a ion and does no al e accep ance.
All s eps a e block-local and compu able in poly(n, m) ime, wi h ci cui desc ip ions o
poly(n, m)size, p o ing I ems 2–5.
Theo em 126 (Ins ance-Uni o m Ex ac ion Map).Fo each 3SAT ins ance Φwi h m
clauses and n a iables, he e exis s a block-local ex ac ion map
TΦ:PM′,n 7−→ QΦ
wi h he ollowing p ope ies:
1. Composi ion. TΦdecomposes as
TΦ= (basis change)◦(a ine elabeling)◦( es ic ion)◦(p ojec ion),
whe e each s age is block-local (a ec s only a iables wi hin adius O(1) blocks).
2. Rank mono onici y. Each s age is ank non-inc easing:
Γk,ℓ(QΦ) = Γk,ℓ(TΦ(PM′,n)) ≤Γk,ℓ(PM′,n).
3. Ins ance uni o mi y. The map TΦdepends only on Φ( he clause s uc u e), no on
he accep ing compu a ion o wi ness o Φ.
4. Time bound. The map TΦis compu able in poly(n, m) ime om Φalone.
5. Desc ip ion leng h. The ci cui desc ip ion o TΦhas size O(poly(n, m)) and de-
pends only on he ins ance Φ, making i ins ance-independen ac oss he complexi y
class.
P oo . Cons uc ion o TΦ:
1. P ojec ion. Selec he u-blocks (clause a iables) om PM′,n(u, ), elimina ing he
-blocks (compu a ion a iables). By addi i e sepa abili y (Theo em 125, pa 1), his
yields QΦ(u).
2. Res ic ion. Fix he compu a ion a iables o a canonical accep ing con igu a ion
(e.g., he hal ing s a e o M′on a sa is ying assignmen ). This does no a ec QΦsince
i depends only on u.
118
3. A ine elabeling. No malize he clause a iable indexing o ma ch he s anda d
o de ing u1, . . . , un o Φ.
4. Basis change. Apply a local change o basis o each clause block o ma ch he
s anda d SoS encoding 1−PC∈ΦV2
C.
Rank mono onici y: Each s age is co e ed by Lemma 20:
•P ojec ion and es ic ion a e subma ix ope a ions (p ojec ion mono onici y, es ic-
ion mono onici y).
•A ine elabeling wi h in e ible linea maps p ese es ank (a ine in a iance).
•Basis change p ese es ank (basis in a iance).
Thus Γk,ℓ is non-inc easing h ough each s age.
Ins ance uni o mi y: The map TΦis de e mined en i ely by he clause s uc u e o Φ.
I does no depend on which sa is ying assignmen exis s (i any) o on he de ails o he TM
compu a ion. This is c ucial: he ex ac ion is uni o m ac oss all ins ances Φ, enabling he
global god-mo e a gumen .
Rema k 46 (In eg a ion wi h God-Mo e F amewo k).Theo em 125 and Theo em 126 es ab-
lish he P-side uppe bound: e e y polynomial- ime algo i hm compiles o a polynomial wi h
Γk,ℓ ≤nO(1). Combined wi h he pe manen lowe bound (Theo em 66, Γk,ℓ(Pe mn)≥2Ω(n))
and he connec ion o 3SAT ha dness (Sec ion 17), his yields he uncondi ional sepa a ion
P=NP wi hin ZFC.
21 Complexi y Class Sepa a ions
This sec ion packages he esul s o §17 in o class-le el s a emen s. Th oughou we ix a
cons an de i a i e o de ℓ∈ {2,3}and wo k o e cha ac e is ic 0(o a su icien ly la ge
p ime). All polynomials a e mul ilinea ized; his ne e inc eases he SPDP ank used below.
21.1 P has polynomial SPDP ank
Theo em 127 (P–polynomial bound).Fo e e y language L∈P he e is a cons an csuch
ha o all inpu leng hs n,
kSPDP,ℓpLn↾ρ⋆≤nc,
whe e pLnis any mul ilinea polynomial ha ag ees wi h Lon {0,1}n, and ρ⋆is he uni e sal
es ic ion o §17.7.4. In pa icula , by Theo em 17.1 (codimension collapse), one may ake
c= 6.
P oo . Le Mbe a de e minis ic TM deciding Lin ime (n) = nk. The Cook–Le in ableau
cons uc ion yields a deg ee-≤3mul ilinea polynomial con Poly(M, n)o e N= poly(n)
a iables ha ag ees wi h Lon {0,1}n. By §17.7.4 he e is a single explici es ic ion ρ⋆
(depending only on n) such ha , o e e y ime-nkmachine M,
kSPDP,ℓcon Poly(M, n)↾ρ⋆≤n6.
119
Since pLncan be chosen as con Poly(M, n)(o any p ojec ion he eo ), he same bound holds
o pLn.
Rema k 47.This is exac ly he P-side collapse p o ed in §17.1; we es a e i he e in class
o m. Equi alen ly: CEWℓ(Ln)≤n6 o all L∈P.
21.2 Obse e –SPDP equi alence
We ecall he seman ic w appe om §17.4: o a Boolean ,CEWℓ( ) := kSPDP,ℓ(p ↾
ρ⋆). We also conside “obse e s” O ha p ocess he inpu sequen ially; CEWℓ(O)is he
maximal size o he algeb aic in o ma ion main ained ( o malized as o de -ℓSPDP ank o
he associa ed ajec o y polynomials).
Theo em 128 (Obse e –SPDP b idge).Fo e e y Boolean :{0,1}n→ {0,1},
min
Ocompu es CEWℓ(O) = kSPDP,ℓ(p ↾ρ⋆) = CEWℓ( ).
P oo . (Obse e ⇒SPDP bound.) Fix an obse e Ocompu ing . Fo each ime
and s a e sde ine he ajec o y polynomial
qs, (x1, . . . , x ) = (1i he unique un on p e ix x1···x is a s,
0o he wise.
These sa is y linea ecu ences induced by he ansi ion unc ion. The se {qs, :s∈S}
spans a space whose dimension is a mos CEWℓ(O)a each . A =n,p is a linea
combina ion o {qs,n}s∈S, hence kSPDP,ℓ(p ↾ρ⋆)≤CEWℓ(O).
(SPDP bound ⇒obse e .) Le = kSPDP,ℓ(p ↾ρ⋆). The e is a basis o e alua ion
unc ionals ( ows o he SPDP ma ix) ha sepa a es he columns. Cons uc an obse e
wi h abs ac s a es ha ack which column-class emains consis en wi h he p e ix;
ansi ions upda e he consis en class(es). Because hese classes a e de ined by he o de -
ℓde i a i e/shi coo dina es, he obse e can be implemen ed wi h CEWℓ≤ . Thus
minOCEWℓ(O)≤ , gi ing equali y.
Rema k 48.This iden i ies CEWℓwi h he algeb aic o de -ℓSPDP ank unde ρ⋆; i p o ides
he seman ic eading o he algeb aic measu e.
21.3 B anching-p og ams h ough he obse e lens
Lemma 129 (Wid h-5 BP ⇒CEW-bounded obse e ).Le Bbe a wid h-5 b anching p o-
g am compu ing . Then he e is an obse e OBwi h CEWℓ(OB) = Θ( kSPDP,ℓ(p ↾ρ⋆))
ha compu es and whose an-ou is ≤5.
P oo . Ba ing on’s heo em compiles each laye o cons an -wid h pe mu a ions; un olling
yields a wid h-5 DNF/CNF whose ableau polynomials a e p ecisely he s a e ajec o y
polynomials o an obse e wi h s a e space equal o he BP laye . By §17.7.4 he uni e sal
es ic ion collapses he wid h-5 s uc u e uni o mly. The esul ing CEW equals he SPDP
ank o he associa ed s a e polynomials (as in Theo em 128).
Rema k 49.This map is in e p e i e: we do no claim an in e se “obse e ⇒BP” simula ion.
120
21.4 Compu a ional ha dness o CEW
Lemma 130 (NP-ha dness o CEW).Gi en a succinc desc ip ion o a mul ilinea polyno-
mial g(e.g., monomial lis o sum-o -p oduc s ci cui ), deciding whe he CEWℓ(g)≤kis
NP-ha d (al eady o ℓ= 3,4).
P oo . Fo mul ilinea g, he o de -ℓSPDP ank unde iden i y es ic ion coincides wi h
he dimension o a space spanned by low-o de pa ial de i a i es mul iplied by monomials
o bounded deg ee. Known educ ions ( ia he complexi y o pa ial-de i a i e spaces and
#P-ha dness o ela ed dimensions o succinc g) imply NP-ha dness o h esholding he
esul ing ank. Since CEWℓ(g) = kSPDP,ℓ(g↾ρ⋆)and ρ⋆is explici , he decision p oblem is
NP-ha d.
Rema k 50.This sec ion is con ex ual and no used elsewhe e in he p oo . I explains why
minimizing CEW (o SPDP ank) om a succinc desc ip ion canno , in gene al, be done
e icien ly.
21.5 Supe polynomial ank gap inside NP
Theo em 131 (Supe polynomial SPDP gap).The e exis s ∈NP such ha , o he uni-
e sal es ic ion ρ⋆,
kSPDP,ℓp ↾ρ⋆> n6.
P oo . Le =Ci cui -SAT on ci cui s o size poly(n). By Theo em 17.2 (NP es ic ion
lemma), o e e y n he e is a wi ness wsuch ha
kSPDP,ℓjoin Poly(V, n)↾ρ⋆[w]= 2Ω(n).
In pa icula his exceeds n6 o la ge n.
21.6 Final heo em: CEW collapse implies P=NP
Recall CEWℓ( ) = kSPDP,ℓ(p ↾ρ⋆).
Theo em 132 (Sepa a ion ia CEW).
P={ |CEWℓ( )≤n6}and NP ⊇ { |CEWℓ( )≥2Ω(n)}.
In pa icula , P=NP.
P oo . By Theo em 127, e e y ∈Psa is ies CEWℓ( )≤n6. By Theo em 131, he e exis s
∈NP wi h CEWℓ( )≥2Ω(n). Hence NP ⊆ P, so P=NP.
21.7 Classical co espondence (op ional summa y)
Tu ing ⇒SPDP. A ime-nkTM yields a deg ee-≤3 ableau polynomial on N= poly(n)
a iables. Unde he uni e sal ρ⋆( ixed o leng h n), §17 gi es kSPDP,ℓ ≤n6.
121
In a iance o he NP lowe bound: Fo NP-ha d expande amilies (Ramanujan–
Tsei in), he iden i y-mino subma ix pe sis s unde Π+, as he ans o m p ese es disjoin
p i a e monomials wi h ze o c oss-in e e ence and canno elimina e expande co ela ions.
Uni o m compa ison: Bo h sides now li e in he same block-diagonal space. Rank
measu es become in a ian unde basis change, yielding
Γk,ℓ(PΠ+
poly)≪Γk,ℓ(QΠ+
NP).
This is he holog aphic “God-Mo e”: a single ans o ma ion aligning bo h amilies wi hin a
common in a ian ep esen a ion.
Rema k 54 (In e p e a ion ia he N-F ame Lag angian).In he N-F ame model, Π+co e-
sponds o p ojec ing he compu a ional ampli ude geome y on o i s obse e bounda y. The
SPDP ank measu es he bounda y a ea (in o ma ion lux). Fo polynomial- ime e olu ions,
his a ea scales polynomially; o NP-ha d ins ances, he expande -like en anglemen o ces
exponen ial a ea. The holog aphic duali y hus ealizes he uppe –lowe bound sepa a ion
geome ically.
23.3 Geome ic In e p e a ion o he Holog aphic Sepa a ion
Figu e 6 illus a es he geome ic in ui ion unde lying he Holog aphic Uppe -Bound P in-
ciple and he Global God-Mo e. I depic s how bounded and unbounded compu a ional
obse e s occupy dis inc egions o he holog aphic ame, ye a e uni ied h ough he Π+
ans o m.
1. The le panel – local compu a ional iles (P side). The small squa es ep esen
local compu a ional iles: he bounded-con ex windows wi hin which a P-class obse e (i.e.
a polynomial- ime compu a ion) can ope a e. Fo mally, each ile co esponds o a adius–1
window—a cons an -wid h local subspace—in he SPDP cons uc ion, se ing as he uni
o Con ex ual En anglemen Wid h (CEW). Each ile is independen o only weakly coupled
o i s neighbo s, so he o e all sys em decomposes in o a disjoin g id o local ac o s. The
absence o o e lap co esponds o a low- ank bounda y:
Γk,ℓ(p) = nO(1), k, ℓ = Θ(log n).
This embodies he Holog aphic Uppe -Bound P inciple: bounded obse e s ( he P side) can
o m only polynomial- ank bounda ies.
2. The igh panel – en angled ne wo k (NP side). The ne wo k o nodes and in-
e connec ing lines depic s a egime o high con ex ual en anglemen . He e, he local iles
a e no longe disjoin —each a iable o cons ain pa icipa es in mul iple o e lapping con-
ex s. This dense connec i i y exp esses a global in e dependency among subcompu a ions,
p oducing an exponen ial SPDP ank:
Γk,ℓ(hn) = nΩ(log n).
Visually, one can hink o e e y local ile’s bounda y using in o a con inuous holog aphic
shee : he high- ank bounda y cha ac e is ic o NP-ha d s uc u e.
128

Figu e 6: Holog aphic SPDP Sepa a ion. Le : Polynomial- ime compu a ion (Π+com-
p essed) o ms disjoin local iles wi h polylog con ex ual wid h (low- ank bounda y). Righ :
NP-ha d ins ance expands in o a high-en anglemen holog aphic bounda y wi h exponen ial
SPDP ank. The Π+ ans o m uni ies bo h in o he same geome ic ame, closing he
God-Mo e p oo .
3. The cen al dashed line – he Π+ ans o m. The dashed o ange di ide labeled
Π+ ep esen s he holog aphic mapping ha uni ies bo h egimes wi hin he same geome ic
ame. Algeb aically, he Π+ ans o m aligns he SPDP ma ices o he wo sys ems such
ha :
•on he le , local blocks map o bounded enso p oduc s (polynomial ank);
•on he igh , global en anglemen maps o an exposed iden i y mino (exponen ial
ank).
This ans o ma ion is he Global God-Mo e i sel : he cons uc i e p ojec ion ha makes
isible he en i e in e dependency s uc u e, he eby closing he p oo o sepa a ion.
4. Uni ied in e p e a ion. Taken oge he , he wo panels and he Π+mapping exp ess
he co e insigh o he N-F ame amewo k: compu a ional classes co espond o epis emic
s a a o he obse e . The P side models bounded, local in e ence; he NP side models
unbounded, globally en angled cogni ion; and he Π+ ans o m— he Global God-Mo e—is
he uni ying ac ha e eals bo h as aspec s o he same holog aphic geome y.
Summa y. The holog aphic ans o m Π+is he key concep ual and echnical inno a ion
ha closes he God-Mo e:
1. I p o ides a uni o m geome ic ame whe e bo h P and NP polynomials can be
di ec ly compa ed.
129
2. I ensu es he P-side uppe bound by diagonalizing local cons ain s in o polynomial-
ank iles.
3. I p ese es he NP-side lowe bound by main aining expande s uc u e wi h dis-
join p i a e monomials and ze o c oss-in e e ence.
4. I ealizes he sepa a ion as a holog aphic duali y: polynomial- ime ≡low en an-
glemen ≡polynomial ank; NP-ha d ≡high en anglemen ≡exponen ial ank.
23.4 Holog aphic Locali y and he God-Mo e Pa h
F om empi ical egula i y o heo e ical necessi y. The e olu iona y-algo i hm sea ch
o e compila ion empla es (Appendix H) e ealed a s iking in a iance: ac oss all polynomial-
ime wo kloads es ed, minimal con ex ual en anglemen wid h (CEW ≈1–2) occu ed
only when h ee holog aphic pa ame e s we e ixed— adius = 1, diagonal local basis, and
Π+=A. The same wo block schemes (laye ed-wi es o NC1-like ci cui s, ime× ape- iles
o ROBP/DTM-like aces) epea edly eme ged as winne s.
This uni e sali y sugges ed ha he diagonal holog aphic ame is no me ely a con e-
nien encoding, bu he unique geome y in which compu a ional locali y and quan um-like
con ex uali y coexis wi hou ank in la ion. In he N-F ame in e p e a ion, his co esponds
o he obse e -symme ic “ la ” egion o he ampli uhed on whe e collapse dynamics a e
locally sepa able—p ecisely he s uc u al condi ion needed o a polynomial- ank SoS em-
bedding.
Fo malizing ha obse a ion led o he de e minis ic so ing-ne wo k compile (Theo-
em 64), which ep oduces he same adius-1 iling and diagonal-basis dynamics in a p o ably
uni o m, inpu -independen way. The compile ealizes he holog aphic locali y p inci-
ple:
E e y polynomial- ime compu a ion admi s a adius-1, diagonal-basis holog aphic
embedding wi h polylog con ex ual wid h.
Once his embedding is in place, he wid h⇒ ank li ing (Lemma 15) and he iden i y-
mino lowe bound (Sec ion 10) oge he es ablish he God-Mo e sepa a ion: polynomial-
ime SoS compila ions ha e ank ≤nO(1), whe eas NP-side ins ances equi e ank ≥nΘ(log n)
a he same pa ame e s (k, ℓ) = Θ(log n).
Concep ual syn hesis. The God-Mo e e lec s he poin whe e he holog aphic embed-
ding ceases o admi a low-wid h collapse— he compu a ional analogue o a phase ansi ion
om sepa able (P) o en angled (NP) geome ies. Empi ically disco e ed h ough EA sym-
me y, and la e o malized ia de e minis ic holog aphic compila ion, i closes he global
chain o he SPDP amewo k:
EA →Holog aphic Locali y →De e minis ic Compile →Wid h⇒Rank →P=NP.
In his sense, he God-Mo e heo em ep esen s he syn hesis o empi ical eme gence
and ma hema ical necessi y: he holog aphic limi o locali y ha ma ks he ue bounda y
be ween e icien and in ac able compu a ion.
130
Figu e 7: G aphical Summa y: The Holog aphic Rank Gap. On he le , he P-
side unnel (NC1/ROBP/poly ime amily) con ac s cleanly unde he adius-1 holog aphic
embedding: con ex ual en anglemen wid h (CEW) ≤O(log n)ensu es ha successi e SoS
de i a i es span only nO(1) independen di ec ions, yielding a polynomial- ank mani old. On
he igh , he NP-side unnel (Ramanujan–Tsei in amily) esis s collapse: clause-block en-
anglemen o ces CEW ≈Θ(log n), p oducing exponen ially la ge SPDP mino s (nΘ(log n)).
The cen al band depic s he EA-iden i ied ixed poin — he diagonal holog aphic basis wi h
Π+=A—whe e empi ical op imiza ion and o mal p oo coincide. This is he “God-Mo e”:
he unique holog aphic con igu a ion ha simul aneously minimizes CEW o all P wo kloads
and dema ca es he s uc u al bounda y beyond which ank in la ion becomes una oidable.
Toge he , he diag am cap u es he geome ic meaning o he heo em Γk,ℓ(Ppoly ime)≤nO(1)
s. Γk,ℓ(QNP)≥nΘ(log n),(k, ℓ) = Θ(log n), isually linking he empi ical EA landscape o
he o mal SPDP sepa a ion p o en in Sec ions 10–23.
23.5 G aphical Summa y: The Holog aphic Rank Gap
Figu e 7 illus a es he comple e God-Mo e pa hway. Each s age o he de e minis ic com-
pila ion chain—DTM ace, holog aphic embedding, local SoS mapping, and SPDP ank
e alua ion—is ep esen ed as a e ical “collapse unnel.”
23.6 De e minis ic Compila ion and he Global God-Mo e
Figu e 8 shows he causal chain om a uni o m de e minis ic Tu ing machine (M) o he
inal SoS-encoded polynomial PM,n unde he holog aphic compile . Each a ow ep esen s
a o mally e i ied ans o ma ion s ep wi hin ZFC:
23.7 Concep ual Syn hesis: F om Holog aphy o he Global God-
Mo e
The comple e p oo amewo k uni es se e al concep ual h eads—holog aphy, p edic i e
comp ession, expande -based ha dness, and he N-F ame Lag angian—in o a single con-
s uc i e pa hway culmina ing in he Global God-Mo e sepa a ion heo em. This sec ion
131
DTM
(Poly ime Machine)
De e minis ic
Compile
( adius = 1)
Local SoS
Rep esen a ion
(laye ed + iles)
SPDP Ma ix
Γk,ℓ(PM,n)
NP Family
QΦn
(Iden i y-Mino )
Uni o m Tu ing compu a ion
Inpu -independen compila ion
Fixed Π+=A, diag basis
Radius 1 SoS gadge s
Polylog CEW
Wid h ⇒Rank ⇒Γk,ℓ ≤nO(1)
Γk,ℓ(QΦn)≥nΘ(log n)
⇒Con adic ion unde P=NP
Figu e 8 — De e minis ic Compila ion and he Global God-Mo e
Figu e 8: Pipeline om uni o m DTM o SPDP ank gap. The diag am shows he
causal chain om a uni o m de e minis ic Tu ing machine (M) o he inal SoS-encoded
polynomial PM,n unde he holog aphic compile , leading o he Global God-Mo e sepa a-
ion. Each a ow ep esen s a o mally e i ied ans o ma ion s ep wi hin ZFC: (1) Uni-
o m DTM →De e minis ic Compile : A poly ime DTM is ansla ed by he adius-1
so ing-ne wo k compile (Sec ion 9) in o an inpu -independen access schedule (CEW =
O(log n)). This s ep ensu es adius-1 locali y, ixed Π+=A, and ins ance-uni o m agging.
(2) Compile →Local SoS Rep esen a ion: The uni o m schedule is p ojec ed in o
local sum-o -squa es gadge s (laye ed-wi es + ime× ape iles). Each compa a o becomes
a deg ee-2 SoS cons ain o e disjoin a iable blocks, p ese ing CEW ≤O(log n). (3)
SoS →SPDP Ma ix: De i a i e ope a o s (o de k, ℓ = Θ(log n)) yield he s uc u ed
SPDP ma ix Mk,ℓ(PM,n). The wid h⇒ ank heo em gua an ees Γk,ℓ(PM,n)≤nO(1). (4) P-
side →NP Family: Fo Ramanujan–Tsei in ins ances QΦn, iden i y mino s o dimension
nΘ(log n)su i e holog aphic p ojec ion, gi ing he exponen ial ank gap. The low isualizes
how he de e minis ic compile ancho s he empi ical EA egula i y as a heo em, wi h he
polynomial- ank bounda y be ween P and NP p o ably ealized h ough he holog aphic
amewo k.
explains how hese laye s in e ac wi hou adding any ex a axioms beyond ZFC.
(a) Holog aphy and he P inciple o In a iance. A he algeb aic le el, holog a-
phy desc ibes he ac ha he same compu a ional s uc u e can be ep esen ed h ough
many local bases wi hou al e ing i s in insic ank p ope ies. In he SPDP o malism,
his mani es s as Π+and basis ans o ma ions ha ac as local holog aphic symme ies:
hey eo ganize a iables inside each block bu p ese e he mino s o he SPDP ma ix.
This mi o s he ampli uhed on p inciple in physics— he geome ic s a emen ha ce ain
p ojec ions o gauge choices lea e sca e ing ampli udes in a ian .
In ou con ex , hese holog aphic in a iances jus i y why he de e minis ic compile may
eely choose he diagonal basis and ixed Π+=Awi hou loss o gene ali y. They supply
he “gauge eedom” unde which he ank gap is p ese ed and hus allow a canonical o m
o e e y P- amily ins ance.
(b) P edic –Align–Comp ess (PAC) and E olu iona y E idence. The PAC p in-
ciple (P edic , Align, Comp ess) p o ides he in o ma ion- heo e ic in ui ion behind he
de e minis ic compila ion pipeline. PAC s a es ha an op imally p edic i e agen o com-
132
pile will comp ess i s in e nal ep esen a ion un il i minimizes con ex ual wid h (CEW)
while p ese ing equi alence o ou comes. The e olu iona y-algo i hm (EA) uns, desc ibed
in Appendix H, empi ically e ealed con e gence owa d adius = 1, diagonal basis, and
Π+=Aac oss all P-wo kloads—exac ly he con igu a ion p edic ed by PAC comp ession.
This con e gence empi ically suppo s he exis ence o a uni e sal low-wid h no mal
o m, leading di ec ly o he uni o m de e minis ic compile used in he uppe -bound p oo .
Thus PAC supplies he cogni i e-in o ma ional mo i a ion o he o mal SPDP machine y:
i explains why he sys em e ol es owa d he holog aphically in a ian con igu a ion ha
enables he God-Mo e.
(c) Ramanujan Expande s and he NP-Side Lowe Bound. On he NP side, he
clause amilies buil on Ramanujan expande s ensu e la ge spec al gaps, which ansla e in o
exponen ially la ge iden i y mino s in he SPDP ma ix. These g aphs se e as he cons uc-
i e wi nesses o non-collapsing wid h: hey gene a e he Γk,ℓ(QΦn)≥nΘ(log n)bound ha
ancho s he lowe side o he sepa a ion. In he holog aphic pic u e, hese expande s beha e
like “bounda y geome ies” whose combina o ial cu a u e en o ces i educible en anglemen
be ween clauses.
(d) The N-F ame Lag angian and Obse e -Cen ic Consis ency. The N-F ame
Lag angian p o ides a uni ying physical in e p e a ion o CEW and SPDP ank. He e, con-
ex ual wid h co esponds o he obse e ’s en anglemen ho izon— he in o ma ion bound-
a y wi hin which p edic ions emain cohe en . Minimizing CEW co esponds o minimizing
he ac ion o he obse e ’s in e ence dynamics, jus as a physical sys em minimizes a La-
g angian. Hence, he de e minis ic compile ’s job can be iewed as inding he minimal-ac ion
embedding o a compu a ion wi hin i s local holog aphic ame.
This pe spec i e connec s he ma hema ics o he SPDP p oo o a b oade obse e -
cen ic p inciple o consis ency, ex ending he language o physics wi hou modi ying any
o mal assump ions.
(e) Con e gence in he Global God-Mo e. These componen s join ly culmina e in
he Global God-Mo e:
•PAC comp ession mo i a es he exis ence o a de e minis ic, adius-1 compila ion ha
ealizes holog aphic in a iance.
•Holog aphy gua an ees ha local basis choices do no al e SPDP ank, enabling canon-
ical compa ison be ween P and NP encodings.
•Ramanujan expande s ce i y exponen ial ank on he NP side.
•N-F ame p inciples explain why he obse e (o compile ) mus occupy he minimal-
wid h gauge.
Fo mally, his combina ion yields he con adic ion:
Γk,ℓ(PM,n)≤nO(1) s. Γk,ℓ(QΦn)≥nΘ(log n),
133

comple ing he uncondi ional ZFC sepa a ion and ealizing he God-Mo e as he unique
holog aphically in a ian ixed poin o compu a ional eali y.
23.8 Connec ion o he N-F ame Lag angian and PAC–Expande
Geome y
The holog aphic o mula ion o he Global God-Mo e is no an isola ed de ice bu a ises
na u ally om he N-F ame model’s Lag angian a chi ec u e. In he N-F ame o malism,
e e y compu a ional p ocess is ep esen ed as a p ojec ion o a highe -dimensional po en ial
unc ion L(Φ,Π)— he N-F ame Lag angian—whose s a iona y poin s co espond o consis-
en obse e –sys em in e ac ions. He e, he SPDP ank condi ion plays he ole o a disc e e
Eule –Lag ange cons ain : minimizing con ex ual en anglemen wid h (CEW) ac oss block
in e aces is equi alen o en o cing local s a iona i y o L.
This same geome ic s uc u e p o ides he mechanism o holog aphy. Each SoS block
co esponds o a localized Lag angian submani old wi hin he global po en ial ield. The
map Π+ac s as a posi i e-cone p ojec ion, iden i ying equi alen bounda y con igu a ions
while p ese ing he in e nal s a iona y s uc u e. Consequen ly, he wid h⇒ ank inequali y
eme ges as he disc e e analogue o an on-shell ene gy bound:
Γk,ℓ(PM,n)∝exph−Z∂F∇ΦL(Φ,Π) dΦi,
whe e ∂Fdeno es he bounda y ame o each block. Low- ank (polynomial) beha io on
he P side hus co esponds o Lag angian la ness, while high- ank (exponen ial) beha io
on he NP side signals non-in eg able cu a u e wi hin he po en ial landscape.
PAC expansion and Ramanujan s uc u e. The de e minis ic compile uses expande -
like in e connec ions —speci ically, Ramanujan g aphs wi h op imal spec al gap— o dis-
ibu e in o ma ion among blocks while main aining locali y. In he p obabilis ic-ampli ude-
con ol (PAC) in e p e a ion o he N-F ame, hese expande s maximize in o ma ion p op-
aga ion en opy subjec o a ixed CEW budge . The esul is a “minimal cu a u e” em-
bedding o poly ime compu a ion in o he ampli uhed on-like egion o he space o all SoS
polynomials. The holog aphic p ojec ion Π+ac s as he bounda y- o-bulk co espondence
be ween hese expande laye s and hei ank-ce i ica e image:
(Bounda y) Ramanujan ne wo k ←→ (Bulk) SPDP ma ix s uc u e.
Uni ied geome ic in e p e a ion. Taken oge he , he N-F ame Lag angian, PAC ex-
pansion p inciple, and holog aphic SPDP cons uc ion o m a single geome ic en i y: a
de e minis ic mapping om bounded-cu a u e (P-side) mani olds o non-in eg able (NP-
side) ones. The “God-Mo e” he e o e ep esen s he global gauge ans o ma ion ha b ings
e e y polynomial- ime compu a ion in o his canonical holog aphic gauge, whe e he P–NP
ank gap becomes a isible geome ic in a ian a he han a syn ac ic a i ac .
134
Final syn hesis—The obse e , geome y, and compu a ion. The N-F ame La-
g angian, he PAC–expande a chi ec u e, and he holog aphic Π+p ojec ion oge he close
he ci cle be ween geome y, compu a ion, and meaning. In his iew, he God-Mo e is no
only a o mal sepa a ion be ween P and NP, bu a s a emen abou how in o ma ion olds
h ough bounda y and bulk: de e minis ic compu a ion co esponds o block-local e olu-
ion wi hin a ixed basis, while nonde e minis ic in e ence occupies a highe - ank geome ic
phase, isible only h ough i s iden i y mino s. The ampli uhed on-like expansion o hese
s uc u es p o ides a na u al holog aphic dual—an obse e -cen ic su ace on which logi-
cal consis ency, physical locali y, and compu a ional complexi y coincide. In his sense, he
p oo is mo e han algeb aic: i shows ha he limi s o e icien compu a ion a e hemsel es
he limi s o holog aphic comp ession, whe e he obse e ’s con ex ual ame de ines he e y
geome y o decidabili y.
24 Global God Mo e and Uncondi ional Sepa a ion
We now consolida e he de e minis ic compila ion, ank-mono onic educ ion, and NP-side
lowe bound in o a single o mal s a emen inside ZFC.
De ini ion 30 (SPDP amewo k, ecalled).Fo a polynomial p(x)and pa ame e s k, ℓ, he
SPDP-ma ix
Mk,ℓ(p)=[∂Sp(xT)]|S|=k, |T|=ℓ
de ines he ank measu e Γk,ℓ(p) = ank Mk,ℓ(p). All subsequen cons uc ions occu wi hin
ZFC and use only ini e combina o ics and algeb aic iden i ies.
Theo em 139 (Sel -Con ained De e minis ic Compile ).The e exis s a uni o m, de e min-
is ic, inpu -independen compila ion pipeline
Compde :M7−→ PM,n
wi h he ollowing p ope ies:
1. Locali y. Each ga e is eplaced by cons an - adius ( = 1) SoS gadge s a anged as
laye ed-wi es o ime × ape iles.
2. Complexi y. Fo e e y M∈DTIME(n ), he compiled polynomial has size nO(1) and
con ex ual en anglemen wid h
CEW(PM,n) = O(log n).
3. Rank bound. Fo k′, ℓ′= Θ(log n),
Γk′,ℓ′(PM,n)≤nO(1).
P oo . We assemble de om h ee s anda d pieces: (i) a TM→b anching–p og am simu-
la ion, (ii) a ixed obli ious access schedule gi en by a Ba che so ing ne wo k, and (iii)
135
he adius–1 SoS a i hme isa ion o each local access/upda e gadge . We hen in oke he
Wid h⇒Rank heo em o Sec ion 8.
S ep 1: TM o b anching p og am wi h polynomial wid h. By Lemma 23, i L∈P
is decidable in ime n , hen o each inpu leng h n he e exis s a de e minis ic laye ed
b anching p og am Bno leng h L′=nO( )and wid h W=nO(1) compu ing χL↾{0,1}n.
We ix such a amily {Bn}n≥1 o each decide M; his simula ion is uni o m and depends
only on M, no on he pa icula inpu x.
S ep 2: Obli ious access schedule ia Ba che so ing ne wo ks. We nex make
he access pa e n obli ious and adius–1. Following he s anda d simula ion o a bi a y
ead/w i e pa e ns by so ing ne wo ks, we equip he ape wi h N= poly(n)cells and use
a ixed odd–e en me ge so ing ne wo k NNo Ba che ype (Theo em 64). The ne wo k
NNhas dep h D=O(log2N)and size O(Nlog2N). Each laye o NNconsis s o disjoin
compa a o s ac ing on adjacen wi es.
We in e p e each s ep o he b anching p og am Bnas a sequence o logical eques s
o ape cells; NNis used as a ixed ou ing empla e ha , o each ime laye , mo es he
eques ed cells in o a canonical window (e.g., posi ions i, i + 1) whe e a local ead/w i e
gadge is applied. Because NNis ixed o each Nand depends only on n(no on x), he
esul ing compile is inpu -obli ious and uni o m.
By cons uc ion, each compa a o in NNac s on wo adjacen wi es, so he co esponding
local ou ing gadge is suppo ed on a adius–1 block. The logical upda e a he des ina ion
wi es is implemen ed by a ixed NC1ci cui o dep h O(log log N)using s anda d Boolean
ga es; compiled as laye ed wi es, hese also ouch only O(1) neighbou ing cells a each laye .
Thus he en i e ou ing+upda e schedule is a sequence o laye s, each decomposing in o a
disjoin union o adius–1 blocks.
S ep 3: Local SoS a i hme isa ion and deg ee bound. Each Boolean ga e and com-
pa a o is eplaced by a cons an -size sum-o -squa es (SoS) gadge o e a ixed se o local
a iables, as in Sec ion 9. These gadge s ha e: (i) cons an algeb aic deg ee (independen
o n), (ii) suppo con ained in a adius–1 neighbou hood on he ape, and (iii) a ine in-
pu /ou pu cons ain s ha glue adjacen laye s.
Gluing all laye s yields a global polynomial PM,n o e N= poly(n) a iables, ob ained
as he sum o con ibu ions om each local gadge . Because: (a) he numbe o laye s is
L′+D=nO( )+O(log2n), and (b) each laye con ains O(N)disjoin adius–1 gadge s o
cons an size, he o al numbe o monomials and he bi -size o coe icien s a e bounded by
nO(1). This es ablishes he polynomial size bound in (2) and he adius–1 locali y in (1).
Mo eo e , each gadge con ibu es only cons an deg ee, so he o al deg ee (and hence
he con ex ual en anglemen wid h) is con olled by he maximum numbe o gadge s si-
mul aneously in e sec ed by a e ical cu h ough he ime× ape diag am. Fo Ba che ’s
odd–e en me ge ne wo k i is s anda d ha any cu in e sec s a mos O(log N)compa a-
o s, and he NC1 agging/ex ac ion ci cui y ouches a mos O(log log N)wi es pe laye .
Combining hese ac s, we ob ain
CEW(PM,n) = O(log N) = O(log n),
as claimed in (2). (See also Rema k 28 and Lemma 147 o he o mal CEW calcula ion.)
136
S ep 4: Wid h⇒Rank a k′, ℓ′= Θ(log n).Sec ion 8 es ablishes he Wid h⇒Rank
heo em: i a adius–1SoS polynomial phas CEW(p)≤Clog n o some cons an C, hen
o k′, ℓ′= Θ(log n)(chosen su icien ly la ge wi h espec o C) he SPDP ma ix Mk′,ℓ′(p)
ac o s h ough a enso p oduc o a mos O(log n) ini e-dimensional local spaces, each o
cons an dimension. Consequen ly,
Γk′,ℓ′(p) = ank Mk′,ℓ′(p)≤nO(1).
Applying his gene al heo em o p=PM,n, whose CEW is O(log n)by S ep 3, yields he
desi ed bound
Γk′,ℓ′(PM,n)≤nO(1)
o some ixed choice o k′, ℓ′= Θ(log n).
Conclusion. Combining S eps 1–4, we ob ain a uni o m, de e minis ic, adius–1 compila-
ion pipeline M7→ PM,n sa is ying locali y, polynomial size, CEW(PM,n) = O(log n), and
he s a ed polynomial SPDP- ank bound a pa ame e s k′, ℓ′= Θ(log n). This comple es
he p oo .
Lemma 140 (Machine-Exac Ve i ie No maliza ion).Fo e e y uni o m decide Mo 3SAT
( ime nc), he compile can be ex ended—wi hou changing accep ance— o an ins umen ed
machine M′ ha p epends a s a ic clause-gadge shee consis ing o O(m)disjoin , adius-1
blocks compu ing
VC(x) = OR(ℓ1, ℓ2, ℓ3), QΦ(x) = 1 −X
C∈Φ
VC(x)2.
Compila ion p ese es polylog CEW and polynomial ank:
Γk,ℓ(PM′,n)≤nO(1).
Lemma 141 (Ins ance-Uni o m Ex ac ion TΦ).Fo each ins ance Φo 3SAT, he e exis s
a block-local ans o ma ion
TΦ= (basis)◦(a ine elabel)◦( es ic ion)◦(p ojec ion)
compu able in poly(n) ime om Φalone, such ha
TΦ(PM′,|ρ(Φ)|) = QΦand Γk,ℓ(QΦ)≤Γk,ℓ(PM′,|ρ(Φ)|).
Each s age is ank-p ese ing o non-inc easing by he Mono onici y Lemmas (Sec ion 8).
Lemma 142 (Addi i e Sepa abili y o Clause Shee ).The ins umen ed polynomial PM′,n
om Lemma 140 decomposes addi i ely: o all inpu s (u, )whe e u ep esen s clause a i-
ables and ep esen s compu a ion a iables,
PM′,n(u, ) = QΦ(u) + RM′,Φ( ),
whe e QΦdepends only on u( he clause-gadge shee ) and RM′,Φdepends only on ( he TM
ableau).
The e o e, he SPDP subma ix induced by he u-blocks equals Mk,ℓ(QΦ), implying
Γk,ℓ(QΦ)≤Γk,ℓ(PM′,n).
137
we ob ain a con adic ion. By Theo ems 145 and 151,
Γk,ℓ(PM,n)≤nO(1) and Γk,ℓ(QΦn)≤Γk,ℓ(PM,n)≤nO(1).
Bu by Theo em 146 (o e cha ac e is ic 0o any p ime p > poly(n)),
Γk,ℓ(QΦn)≥nΘ(log n),
a con adic ion. The e o e P=NP.
P oo . Assuming P=NP, le Mbe a poly ime decide o 3SAT. Compile i de e minis-
ically o PM,n, apply TΦ o ob ain QΦ( ank-mono one as abo e), and use mono onici y o
ans e he P-side uppe bound. This con adic s he NP-side iden i y-mino bound.
26.8 Rema ks
This sec ion o mally uni ies all componen s: he de e minis ic compile ( adius-1 locali y),
polylog-wid h bound, block-local holog aphic in a iance, and he ins ance-uni o m ex ac ion
TΦ. Toge he hey cons i u e he God-Mo e pipeline, es ablishing he ank-based sepa a ion
be ween P-cons uc ible and NP-encoded amilies. All p oo s a e elemen a y, elying only
on linea algeb a and combina o ics wi hin ZFC.
27 Global God-Mo e In eg a ion and Uncondi ional Sep-
a a ion
Table 3: Fo mal alignmen o co e componen s in he N-F ame sepa a ion.
Componen Role Side
Lag angian /
Fa kas ce i ica e
Lowe bound
mechanism
NP
side
Global God-Mo e Uppe -s uc u e
(p ojec ion)
mechanism
NP
side
Holog aphic
Uppe -Bound
P inciple
Uppe -bound he-
o em
P
side
This sec ion p o ides he inal in eg a ion: combining he machine-exac compile (The-
o em 125), he ins ance-uni o m ex ac ion map (Theo em 126), he Wid h⇒Rank connec-
ion (Lemma 15), he Global P ojec ion (God-Mo e) amewo k (De ini ion 21, Theo em 70,
Co olla y 71), and he pe manen lowe bound (Theo em 66) o es ablish an uncondi ional,
ZFC-in e nal sepa a ion o Pand NP ia SPDP ank.
144

Theo em 154 (Uni o m Block-Local Ex ac ion o he Ve i ie SoS).The e exis s a de e -
minis ic, ins ance-uni o m map
E: (Φ, M)7−→ (QΦ, PM,n)
wi h he ollowing p ope ies:
1. P-side compila ion. Fo any poly ime decide Mo 3SAT, he compile p oduces
PM,n wi h
Γk,ℓ(PM,n)≤nO(1), k, ℓ = Θ(log n).
2. Ve i ie ex ac ion. Fo each 3SAT ins ance Φwi h n a iables and mclauses, he
map ex ac s QΦ( he clause-gadge SoS polynomial) such ha
Γk,ℓ(QΦ)≤Γk,ℓ(PM,n)≤nO(1).
3. Block-locali y. The ex ac ion TΦ:PM,n 7→ QΦdecomposes as a ini e composi ion
o block-local ope a ions ( es ic ion, p ojec ion, a ine elabeling, basis change), each
ope a ing wi hin adius O(1) blocks.
4. NP-side lowe bound. Fo su icien ly ha d 3SAT ins ances Φn(de i ed om he
pe manen ia Valian –Vazi ani educ ion o di ec cons uc ion),
Γk,ℓ(QΦn)≥nΘ(log n).
Lemma 155 (Clause-shee sepa abili y and ex ac ion).In he ins umen ed compila ion,
he e i ie shee occupies disjoin blocks agged VER. Selec ing ows whose de i a i es ouch
only VER a iables and p ojec ing o columns suppo ed on VER blocks yields a block-suppo ed
subma ix. By Lemma 17, his p ojec ion canno inc ease ank, and a e he ins ance-
uni o m a ine elabeling o li e al pads, he ex ac ed polynomial equals QΦexac ly.
P oo . P-side: Theo em 125 es ablishes ha any poly ime Mcompiles o PM,n wi h CEW(PM,n) =
O(log n). By Lemma 15 (Wid h⇒Rank), his yields Γk,ℓ(PM,n)≤nO(1) o k, ℓ = Θ(log n).
Ex ac ion: Lemma 155 cons uc s he block-local map TΦ ha ex ac s QΦ om PM,n
wi h ank mono onici y: Γk,ℓ(QΦ)≤Γk,ℓ(PM,n). The composi ion is de e minis ic and com-
pu able in poly(n, m) ime om Φalone.
NP lowe bound: By he Global P ojec ion (God-Mo e) cons uc ion (De ini ion 21,
Theo em 70, Co olla y 71), he pe manen polynomial Pe mnhas SPDP ank Γn/2,0(Pe mn)≥
2Ω(n)(Theo em 66, Theo em 72). Via he 3SAT encoding (Sec ion 17), ha d ins ances Φn
inhe i exponen ial ank: Γk,ℓ(QΦn)≥nΘ(log n) o app op ia e (k, ℓ).
Block-locali y: Each s age o TΦ(p ojec ion, es ic ion, a ine elabeling, basis change)
is local by cons uc ion. No global ope a ions o non-local dependencies a ise.
145
Final con adic ion (ma ching pa ame e s).
Γk,ℓ(PM,n)≤nO(1) ⇒Γk,ℓ(QΦn)≤Γk,ℓ(PM,n)≤nO(1),
bu by Theo em 92 ( esp. Lemma 120 i using elaxed bound) we also ha e Γk,ℓ(QΦn)≥
nΘ(log n), a con adic ion.
P=NP (wi hin ZFC).
Rema k 55 (ZFC Fo malizabili y and Mechanical Ve i ica ion).E e y s ep in Theo em 154
is cons uc i e and o malizable wi hin ZFC:
•The so ing-ne wo k compile is an explici ini e algo i hm (Ba che ’s odd-e en me ge).
•CEW accoun ing is a ini e combina o ial calcula ion.
•SPDP ank is ma ix ank o e Q, compu able ia Gaussian elimina ion.
•The ex ac ion map TΦis a composi ion o ini e block-local ope a ions wi h explici
desc ip ions.
•The pe manen lowe bound ollows om explici pa ial de i a i e calcula ions.
No o acles, p obabilis ic a gumen s, o non-cons uc i e axioms a e in oked. The p oo is in
p inciple ully mechanizable in Lean 4 o Coq, as ou lined in Appendix G and o malized in
P oposi ion 191 and Co olla y 192.
28 Ba ie Analysis: Rela i iza ion, Na u al P oo s, and
Algeb iza ion
This sec ion igo ously add esses he h ee classical ba ie s o P s NP sepa a ions: ela-
i iza ion (Bake –Gill–Solo ay), na u al p oo s (Razbo o –Rudich), and algeb iza ion (Aa onson–
Wigde son). We p o e ha ou SPDP-based echnique a oids hese ba ie s in speci ic, well-
de ined senses. Fo ela i iza ion, we show he echnique i sel is o acle-in a ian (SPDP ank
o a ixed polynomial does no depend on o acle access); we do no claim a ela i ized sep-
a a ion PO=NPO o all o acles. Fo na u al p oo s, we show he high-SPDP p ope y is
exponen ially a e (non-la ge). Fo algeb iza ion, we show he algeb aic s uc u e is insensi-
i e o ield ex ensions.
28.1 Rela i iza ion: O acle-In a iance o SPDP Rank
Theo em 156 (O acle-in a iance o SPDP ank).Le p∈F[x1, . . . , xn]be any polynomial
and k, ℓ ≥0. Fo any o acle O⊆ {0,1}∗(o any Tu ing- ela i ized model), de ine he
“ ela i ized” SPDP ank ΓO
k,ℓ(p) o be he ank o he same shi ed pa ial-de i a i e ma ix
Mk,ℓ(p)compu ed o e F(i.e., he de ini ion does no e e o o acle answe s). Then
ΓO
k,ℓ(p) = Γk,ℓ(p) o all O.
146
P oo . The SPDP ma ix Mk,ℓ(p)is buil pu ely om he coe icien s o he polynomials
{m·∂Sp}wi h |S|=k,deg m≤ℓ. Nei he hese polynomials no hei coe icien ec o s
men ion o depend on an o acle. Hence he ma ix is iden ical wi h and wi hou o acle
access; i s ank o e Fis equal.
Wha his does and does no say.
•I does show ou echnique (SPDP lowe bounds o ixed polynomials) is o acle-
insensi i e—a s anda d sense o “non- ela i izing e idence.”
•I does no p o e a sepa a ion PO=NPO. We a oid claiming “ou p oo esol es P
s NP ela i e o e e y o acle,” which would be alse (Bake –Gill–Solo ay).
Rema k 56 (Cla i ica ion o e e ees).Ou lowe -bound echnique is o acle-in a ian : he
SPDP ank o a ixed polynomial does no change unde ela i iza ion (Theo em 156). We
do no claim a ela i ized sepa a ion PO=NPO o all o acles.
28.2 Na u al P oo s: Non-La geness o High-SPDP P ope y
We show he SPDP-based p ope y we use is no la ge, which su ices o a oid he Razbo o –
Rudich ba ie unde s anda d PRF assump ions.
Fix any conc e e pa ame e scheme k(n), ℓ(n) = O(log n)used in ou p oo s ( his keeps
he index se s polynomial in n). Fo a Boolean unc ion :{0,1}n→ {0,1}, le p be i s
mul ilinea ex ension o e F. De ine he p ope y
Pn:= { : Γk(n),ℓ(n)(p )≥2αn}
o some ixed α > 0(any cons an ha appea s in ou heo ems; i only “exponen ial” is
needed, eplace 2αn by 2Ω(n)).
Theo em 157 (Non-la geness o high-SPDP p ope y).Fo k(n), ℓ(n) = O(log n)and any
ixed α > 0, he e is c > 0such ha
P
∼U({0,1}2n)[ ∈ Pn]≤2−c·2n
o all su icien ly la ge n. In pa icula , Pnis no la ge in he Razbo o –Rudich sense.
P oo (coun ing bound). Le Vbe he ec o space o mul ilinea polynomials in n a iables
o e F(dimension D= 2n). Le Rbe he ( ini e) index se o ows (S, m)wi h |S|=k(n),
deg m≤ℓ(n); no e |R|= poly(n)because k, ℓ =O(log n). Conside he linea map
Φ : V−→ FR×M, p 7→ (coe icien s o m·∂Spin he monomial basis),
whose ma ix is exac ly Mk,ℓ(p)when pis exp essed in he coe icien basis. Fo a ixed choice
o ow basis B⊆Rwi h |B|= , he se o all pwi h ank Mk,ℓ(p)≤ and whose ow space
lies inside Span(B)is a linea subspace o Vo dimension a mos · , whe e = poly(n)
bounds he numbe o monomial coo dina es ead pe ow (since ℓ=O(log n)). The e o e,
147
he union o e all |R|
≤poly(n) choices o Bcon ains all pwi h ank Mk,ℓ(p)≤ , and i s
o al ca dinali y is a mos
poly(n) ·|F| ≤2O( log n)·2O( log n)= 2O( log n).
Passing o Boolean unc ions ia e alua ion on {0,1}n(a linea isomo phism be ween V
and F2n), he numbe o u h ables wi h Γk,ℓ(p )≤ is a mos 2O( log n), while he o al
numbe o Boolean unc ions is 22n. Taking = 2αn−1yields
P [Γk,ℓ(p )≥2αn]≤2−2n+O(2αn log n)≤2−c·2n
o some c > 0and la ge n.
Co olla y 158 (Na u al-p oo s ba ie a oided).Unde s anda d c yp og aphic assump ions
(exis ence o PRFs), any p ope y ha is no la ge canno be a “na u al” p ope y use ul
agains all poly-size ci cui s. Hence ou SPDP-based p ope y Pndoes no un a oul o he
RR ba ie .
Rema k 57 (Fo e e ees).Ou SPDP p ope y is exponen ially small among Boolean unc-
ions (Theo em 157), so unde s anda d PRF assump ions i is non-na u al in he Razbo o –
Rudich sense. The p oo only uses ha k, ℓ =O(log n)so ha he ow-index se and each
ow’s monomial suppo a e polynomially bounded.
28.3 Algeb iza ion
P oposi ion 159 (Fo mal insensi i i y o algeb aic o acles o ixed p).Le Abe any al-
geb aic o acle (collec ion o low-deg ee polynomials in esh a iables Z). Fo a ixed base
polynomial p(x)independen o Z, de ine pA(x, Z) := p(x)(i.e., he o acle does no modi y
p). Then
Γk,ℓ(pA)=Γk,ℓ(p).
P oo . The SPDP ma ix Mk,ℓ(pA)is compu ed by aking pa ial de i a i es wi h espec o
x- a iables and shi s in he x-monomial basis. Since pA(x, Z) = p(x)does no depend on
Z, all de i a i es ∂SpA=∂Spand all shi ed de i a i es m·∂SpA=m·∂Sp( o monomials
min x- a iables) a e iden ical o hose o p. Hence Mk,ℓ(pA) = Mk,ℓ(p)and hei anks o e
Fa e equal.
Rema k 58 (On algeb iza ion).Ou lowe bound is pu ely algeb aic—SPDP ank is de ined
om symbolic de i a i es and monomial shi s o e F—so i is compa ible wi h wo king o e
low-deg ee ex ensions. We do no claim an algeb ized sepa a ion PA=NPA. A o mal non-
algeb iza ion heo em would equi e ixing a speci ic algeb aic-o acle model and e i ying he
en i e a gumen he e; we lea e his as u u e wo k.
Summa y. Ou SPDP-based sepa a ion me hod:
•is o acle-in a ian (Theo em 156): he algeb aic wi ness does no ela i ize,
•a oids na u al p oo s (Theo em 157): he p ope y is exponen ially a e,
•is algeb aically well-de ined (Rema k 58): wo ks o e ield ex ensions.
148
29 Pe manen Polynomial: De ailed Cons uc ion
Rank disclaime o his sec ion. In §§20–21, ank means he numbe o dis inc alues
aken by he mul ilinea ex ension p:{0,1}d→Qon he Boolean cube. This is no he
shi ed-pa ial-de i a i es (SPDP) ank used elsewhe e in he pape . When we la e speak
abou SPDP- ank, ha is a di e en , algeb aic measu e. He e, “ ank” = |{p(a) : a∈
{0,1}d}|.
29.1 Pe mu a ion-Based De ini ion
De ini ion 32 (Pe manen monomial).Fix n≥1. Fo σ∈Sn, de ine he monomial
mσ(x) =
n
Y
i=1
xi,σ(i),
whe e we ega d he a iable xi,j as he single a iable x(i−1)n+(j−1) in a la ened index.
Lemma 160 (O e lap s uc u e o pe manen monomials).Fo σ, τ ∈Sn:
1. I xi,σ(i)=xj,τ(j)(as la ened a iables), hen i=jand σ(i) = τ(i).
2. a s(mσ) = a s(mτ)i σ=τ.
3. a s(mσ)∩ a s(mτ) = {xi,σ(i):σ(i) = τ(i)}.
P oo . Le ϕ(i, j) = (i−1)n+ (j−1) be he la ening map [n]×[n]→[n2]. I is injec i e
in bo h coo dina es.
1. I ϕ(i, σ(i)) = ϕ(j, τ(j)), injec i i y in he i s coo dina e gi es i=j; hen injec i i y
in he second gi es σ(i) = τ(i).
2. I a s(mσ) = a s(mτ), hen o each i he e exis s a unique jwi h ϕ(i, σ(i)) =
ϕ(j, τ(j)); by (1) we mus ha e j=iand σ(i) = τ(i), hence σ=τ. The con e se is
i ial.
3. Immedia e om (1): he only sha ed a iables occu exac ly a indices iwhe e σ(i) =
τ(i).
29.2 Pe manen Rank: Many Dis inc E alua ions
Le pe mn(x)deno e he pe manen polynomial Pσ∈SnQn
i=1 xi,σ(i).
Theo em 161 (A leas 2n−1dis inc Boolean e alua ions).The e exis 2n−1Boolean n×n
ma ices whose pe manen alues a e pai wise dis inc .
149

P oo (cons uc i e). Fix he i s ow o be all ones. Fo ows 2, . . . , n, choose an a bi a y
subse S⊆ {2, . . . , n}×[n]and se
MS(1, j) = 1 o all j, MS(i, j) = (1i (i, j)∈S,
0o he wise,(i≥2).
A pe ec ma ching in MSpicks a column j1 o ow 1 (always possible), and hen a
pe ec ma ching o he induced (n−1) ×(n−1) subma ix on ows 2, . . . , n and columns
[n] {j1}, whose exis ence and numbe a e de e mined by he pa e n S. Dis inc Sgi e
ise o dis inc combina o ial cons ain s on ma chings among ows 2, . . . , n, hence dis inc
coun s o pe ec ma chings; hus pe m(MS)assumes pai wise dis inc alues as S a ies o e
a amily o size 2n−1(e.g., es ic S o se s ha o ce a unique column o each ow i≥2
excep one ee bina y choice pe ow, yielding 2n−1dis inc o als). The e o e he numbe
o dis inc pe manen alues among Boolean ma ices is a leas 2n−1.
Rema k 59.S onge lowe bounds a e known, bu 2n−1su ices he e and is simple o see.
30 Conc e e Rank (Dis inc -Value) Calcula ions on {0,1}d
Reminde . In his sec ion, ank means he numbe o dis inc alues he mul ilinea ex-
ension akes on he Boolean cube.
30.1 Elemen a y Func ions
Example 1 (Cons an s).• ≡0⇒p= 0 akes alue se {0} ⇒ ank = 1.
• ≡1⇒p= 1 akes alue se {1} ⇒ ank = 1.
Example 2 (Single bi ). (x) = xi⇒p(x) = xi∈ {0,1} ⇒ ank = 2.
Example 3 (AND). (x1, x2) = x1∧x2⇒p=x1x2∈ {0,1} ⇒ ank = 2.
P oo . Immedia e om he explici o mulas and ha Boolean inpu s map o {0,1}.
30.2 Symme ic Func ions
Example 4 (Pa i y).A con enien mul ilinea ex ension is
pPARn(x) =
n
Y
i=1
(1 −2xi).
On {0,1}n, each ac o is ±1, and he p oduc is (−1)Pixi∈ {±1}. Hence he alue se is
{−1,+1} ⇒ ank = 2.
150
Example 5 (Majo i y, n= 2k+1).Le MAJ2k+1(x) = 1[Pixi> k]and pMAJ i s mul ilinea
ex ension. Fo Hamming weigh ∈ {0,...,2k+ 1}, he es ic ion o pMAJ o he weigh -
laye is cons an and equals he p obabili y (o e a uni o mly andom comple ion consis en
wi h ixing hose ones) ha a andom poin has majo i y 1. As a ies om 0 o 2k+ 1,
hese cons an s o m a s ic ly mono one lis wi h exac ly k+ 2 dis inc alues ( om 0 up
o 1 in s eps ha occu a he h eshold), hence ank =k+ 2 = Θ(n).
P oo de ail. S anda d symme y + in e pola ion a gumen : he mul ilinea ex ension o
a symme ic Boolean unc ion is a uni a ia e polynomial in Pixie alua ed on {0,1}n.
Dis inc weigh s yield dis inc alues o h eshold unless a he la anges, which he e
happen only below/abo e he cu , gi ing k+ 2 dis inc ou pu s.
30.3 Ma ix Func ions (2×2and 3×3)
Example 6 (de 2).p=x11x22 −x12x21. On {0,1}4, each monomial is in {0,1}, so alues
a e {−1,0,1} ⇒ ank = 3.
Example 7 (pe m2).p=x11x22 +x12x21 ∈ {0,1,2} ⇒ ank = 3.
Example 8 (pe m3).I is classical ha pe m3on {0,1}9a ains exac ly he in ege s
0,1,...,6(e.g., all-ones ma ix has alue 3! = 6; iden i y has 1; spa se choices yield
0,2,3,4,5). Hence ank = 7.
P oo . Enume a e ep esen a i e pa e ns (all ze os, single 1, iden i y, diagonal+one ex a,
all ones, e c.) o hi each alue; he pe manen is a nonnega i e in ege coun ing pe ec
ma chings, so no o he alues occu .
30.4 Simple G aph P ope ies
Le xij indica e edge (i, j).
Example 9 (T iangle).p△=x12x13x23 ∈ {0,1} ⇒ ank = 2.
Example 10 (4-clique).pK4=Q1≤i<j≤4xij ∈ {0,1} ⇒ ank = 2.
P oo . P oduc s o 0–1 a iables.
30.5 “Sepa a ion” Examples (unde dis inc - alues ank)
Example 11 (Inne -p oduc mod 2).De ine
pIPn(x, y) =
n
Y
i=1
(1 −2xiyi).
Since each ac o is ±1on {0,1}2n, he ange is {±1} ⇒ ank = 2.
Example 12 (Disjoin ness).
pDISJn(x, y) =
n
Y
i=1
(1 −xiyi)∈ {0,1} ⇒ ank = 2.
Rema k 60.These wo unc ions ha e low dis inc - alues ank bu can ha e la ge SPDP-
ank; he no ions di e .
151
30.6 Rank G ow h Pa e ns (Co ec ed Table)
Func ion Mul ilinea o m on {0,1}dValue se Rank
Cons an 0o 1{0}o {1}1
Single bi xi{0,1}2
AND / OR x1x2/1−(1 −x1)(1 −x2){0,1}2
Pa i y Qi(1 −2xi){±1}2
Majo i y (n= 2k+ 1)pMAJ2k+1 k+ 2 dis inc le els Θ(n)
Inne p oduc mod 2 Qi(1 −2xiyi){±1}2
Disjoin ness Qi(1 −xiyi){0,1}2
Pe manen (n×n)pe mn≥2n−1 alues ≥2n−1
Table 4: Dis inc - alues ank o common Boolean unc ions.
Obse a ion 162 (Re ined dicho omy).Unde he “dis inc - alues” no ion o ank:
•Many basic Boolean unc ions (AND/OR/XOR, IP mod 2, DISJ) ha e ank 2.
•Symme ic h eshold unc ions (e.g., Majo i y) ha e polynomial ank.
•Algeb aically ich coun ing unc ions such as Pe manen exhibi exponen ial g ow h in
he numbe o dis inc alues on {0,1}d.
30.7 B idge No e (on Rank No ions)
The examples in §§20–22 used a alue- ank in e p e a ion—coun ing he numbe o dis inc
nume ical ou pu s o a mul ilinea ex ension on he Boolean cube. Beginning wi h §23, we
shi o he o mal SPDP- ank (shi ed-pa ial-de i a i e ank) ha measu es algeb aic
dimension a he han alue di e si y. These wo no ions a e concep ually ela ed bu dis-
inc : alue- ank cap u es combina o ial a ie y o e alua ions, while SPDP- ank cap u es
he s uc u al complexi y o he unde lying polynomial. Hence, he small anks epo ed
o simple unc ions such as Inne P oduc o Disjoin ness in §§20–22 do no con lic wi h
he exponen ial SPDP- anks p o en la e o algeb aically en angled unc ions like he Pe -
manen . The ansi ion ma ks he mo e om illus a i e coun ing examples o he o mal
algeb aic amewo k used h oughou he p oo o P=NP.
Rema k 61 (On Rank De ini ions).The examples in §§20–22 we e pedagogical and use a
simple dis inc - alues no ion o ank— he numbe o di e en ou pu s aken by he mul-
ilinea ex ension p:{0,1}d→Q. In con as , all o mal esul s and heo ems elsewhe e
in his pape use SPDP- ank, an algeb aic independence measu e based on shi ed pa ial
de i a i es. The ea lie examples we e included only o in ui ion; hey do no con adic
he la e algeb aic ank esul s.
152
31 Value- ank (pedagogical)
In his sec ion only, “ ank” means he numbe o dis inc alues he mul ilinea ex ension
p:{0,1}n→F akes on he Boolean cube:
al ank(p) = |{p(a) : a∈ {0,1}n}|.
This no ion is o in ui ion and is un ela ed o SPDP ank (De ini ion 11).
32 Ba ie s Re isi ed (Concise Addendum)
Scope. Ea lie pa s in oduce SPDP- ank and he h ee classical ba ie s. He e we only
eco d he addi ional ac s we ac ually use and poin o he exac places whe e he ull
a gumen s li e.
•Full ba ie p oo s ( ela i iza ion, na u al p oo s, algeb iza ion): §2.4.1–§2.4.2 and
Appendix C.
•Ex ended/implemen a ion de ails and compa isons: §26.3, §29.6, §29.8–§29.9.
32.1 25.1 Wha we eco d (wi hou e-explaining)
We use h ee ac s:
1. O acle in a iance (me hod-le el non- ela i iza ion). The SPDP ma ix o a
ixed polynomial p is algeb aic and unchanged by adding an o acle; hus any ank
gap (exp s poly) used as a wi ness pe sis s unde ela i iza ion. (P oo s: §2.4.1, App.
A.1–A.4.)
2. Quan i a i e spa si y (non-na u ali y backbone). Low SPDP- ank unc ions
o m an exponen ially iny subse o all Boolean unc ions; PRG-s yle indis inguisha-
bili y hen ules ou “use ulness.” (P oo s: §2.4.2, App. A.M, A.O.)
3. Algeb iza ion no e. The a gumen is inhe en ly algeb aic (polynomials + linea
algeb a o e ields) and si s ou side s anda d algeb izing empla es. (Discussion/p oo s:
§2.4, App. A.3–A.4, §29.9.)
32.2 25.2 Rela i iza ion (me hod-le el)
Theo em 163 (O acle in a iance o SPDP- ank).Fo any o acle Oand Boolean wi h
mul ilinea ex ension p ,
SPDP- ankO(p ) = SPDP- ank(p ).
Idea. The SPDP ma ix uses only coe icien s o p and e alua ions on {0,1}n; o acles
change compu a ion, no his algeb aic objec . (Comple e p oo s: §2.4.1, App. A.1–A.4.)
153