Geome ic Complexi y Hie a chy and Complexi y
Classes
in Compu a ional Uni e se:
Volume G ow h, Cu a u e, and Compu abili y
Bounda ies
Unde Uni ied Time Scale
Haobo Ma1Wenlin Zhang2
1Independen Resea che
2Na ional Uni e si y o Singapo e
No embe 24, 2025
Abs ac
In p e ious sys ema ic s udies o “compu a ional uni e se” Ucomp = (X, T,C,I),
we ha e successi ely cons uc ed disc e e complexi y geome y, disc e e in o ma-
ion geome y, con ol mani old (M, G) induced by uni ied ime scale, ask in o -
ma ion mani old (SQ, gQ), ime–in o ma ion–complexi y join a ia ional p inciple,
and es ablished equi alence be ween physical uni e se ca ego y and compu a ional
uni e se ca ego y on e e sible quan um cellula au oma on (QCA) subclass. On
he o he hand, complexi y classes (such as P, NP, BQP) in classical complexi y
heo y a e mainly de ined h ough “uppe bound o s eps/ga es as inpu size n
a ies”, lacking sys ema ic co espondence wi h geome ic s uc u es.
This pape p oposes wi hin compu a ional uni e se geome ic amewo k a geo-
me ic complexi y hie a chy heo y: h ough complexi y dis ance dcomp, com-
plexi y ball olume g ow h Vx0(T), disc e e Ricci cu a u e, and geodesic s uc u e
o con ol mani old (M, G), we gi e geome ic cha ac e iza ions o a amily o na -
u al complexi y classes, and p o e se e al cons ain heo ems o o m “complexi y
class ↔geome ic in a ian s”.
Speci ically, we i s in oduce in o compu a ional uni e se inpu encoding am-
ily {ιn: Σn→X}, iewing decision o language L⊂Σ∗as eachabili y p oblem
om inpu con igu a ion o “accep ance egion” A⊂X. Fo each inpu leng h
n, we use complexi y dis ance o de ine minimum compu a ion adius TL(n), and
acco dingly in oduce geome ic complexi y classes
GC(poly) = {L:TL(n)≤Cnk},GC(exp) = {L:TL(n)≤2O(n)},
e c. We p o e: unde na u al “Tu ing–QCA–compu a ional uni e se equi a-
lence” assump ion, GC(poly) is equi alen o adi ional P class (di e ing by a
mos polynomial escaling), while GC(exp) co e s EXP class.
1
Second, we in oduce olume g ow h and complexi y dimension in o geome ic
scaling o complexi y classes: o gi en basepoin x0and complexi y ball BT(x0),
olume g ow h exponen
dimcomp(x0) = lim sup
T→∞
log Vx0(T)
log T
is used o cha ac e ize “dimension” o local compu a ion space. We p o e a
polynomial dimension cons ain heo em: i in some egion dimcomp(x0)≤
d, and all ela ed language decision ajec o ies a e con ined o ha egion, hen
geome ic complexi y unc ions TL(n) o all hese languages a e a mos polynomial,
wi h exponen kcon olled by d. Con e sely, in egions whe e nega i e cu a u e
leads o exponen ial olume g ow h, we can cons uc language amilies whose
geome ic complexi y unc ions necessa ily each o app oach exponen ial le el,
e lec ing “nega i e cu a u e ↔exponen ial complexi y” geome ic–complexi y
connec ion.
Thi d, we in oduce geome ic complexi y ho izon: o gi en basepoin and
g ow h o de (n), de ine language amily decidable wi hin adius (n), and use
disc e e Ricci cu a u e lowe bound wi h olume compa ison heo em o p o e:
in non-nega i e cu a u e egions, i olume g ow h bounded by polynomial uppe
bound, hen he e exis no “geome ically essen ially exponen ially ha d” languages;
while in local s ong nega i e cu a u e egions, he e exis na u al language ami-
lies whose complexi y ho izons necessa ily exceed any gi en polynomial adius.
Finally, we discuss quan um case: in QCA uni e se, h ough analysis o con ol–
sca e ing mani old (M, G) and phase in e e ence s uc u e, we gi e geome ic
uppe bound o BQP class: unde p emises o uni ied ime scale and app op ia e
in e e ence egula i y, minimum geodesic leng h on con ol mani old o languages
in BQP s ill bounded by polynomial uppe bound, while olume explosion and
nega i e cu a u e mo e a ec “non-in e e ence-exploi able” classical complexi y
pa .
This pape sys ema ically connec s adi ional complexi y classes wi h geome -
ic in a ian s ( olume g ow h, cu a u e, ho izons) in compu a ional uni e se, p o-
iding ounda ion o subsequen geome iza ion o highe -le el concep s such as
“complexi y phase ansi ions” and “capabili y– isk on ie s”.
Keywo ds: Compu a ional uni e se; Geome ic complexi y; Complexi y classes; Volume
g ow h; Ricci cu a u e; Complexi y ho izon; BQP; Uni ied ime scale
1 In oduc ion
Classical complexi y heo y usually de ines complexi y classes based on abs ac models
(Tu ing machines, Boolean ci cui s, quan um ci cui s, e c.). Fo example, P class consis s
o languages decided by de e minis ic Tu ing machines wi h polynomial s eps, NP class
consis s o languages whe e polynomial-leng h e idence can be e i ied in polynomial
ime, BQP class consis s o languages decidable by polynomial-size quan um ci cui s
wi h bounded e o .
These de ini ions highly depend on speci ic models, al hough such models a e mu ually
equi alen in polynomial ime, complexi y classes hemsel es lack uni ied geome ic–
s uc u al cha ac e iza ion:
Do p oblems wi hin P class possess some common geome ic ea u es in “compu a-
ion space” (e.g., local olume g ow h bounded, non-nega i e cu a u e)?
2
Do non-P classes (e.g., ypical NP-ha d p oblems) necessa ily exhibi geome ic
ea u es o “nega i e cu a u e + exponen ial olume explosion” in ce ain egions?
Can BQP class ad an age ela i e o P class be unde s ood as “exploi ing addi ional
in e e ence s uc u e unde same geome ic backg ound”?
In p e ious “compu a ional uni e se” amewo k, we ha e in oduced geome ic ob-
jec s sui able o bea ing hese ques ions:
1. Dis ance dcomp, olume g ow h Vx0(T), complexi y dimension dimcomp(x0), and dis-
c e e Ricci cu a u e κ(x, y) on complexi y g aph Gcomp = (X, E, C);
2. Con ol mani old (M, G) unde uni ied ime scale, whose geodesic dis ance dGap-
p oxima es disc e e complexi y dis ance;
3. Con igu a ion–in o ma ion mapping ΦQ:X→ SQand ask in o ma ion mani old
(SQ, gQ), p o iding geome ic backg ound o “inpu –ou pu seman ics”.
This pape aims o use hese ools o pe o m geome ic s a i ica ion o complexi y
classes:
De ine language geome ic complexi y unc ion TL(n) using complexi y dis ance;
Use olume g ow h and dimension o cha ac e ize “how many di e en compu a ion
pa hs and ou pu s a egion can accommoda e”;
Use cu a u e o desc ibe “local pa h di e gence/con ac ion s uc u e”, he eby
e lec ing “local ha dness”;
Use complexi y ho izon o cha ac e ize “wi hin wha adius ce ain class o decision
can be comple ed”.
We i s gi e de ini ions o geome ic complexi y classes unde comple ely gene al
compu a ional uni e se se ing, hen unde “Tu ing–QCA–compu a ional uni e se equi -
alence” assump ion, connec hese geome ic classes wi h adi ional complexi y classes.
2 P elimina ies: Compu a ional Uni e se, Complex-
i y Geome y, and Inpu Encoding
2.1 Re iew o Compu a ional Uni e se and Complexi y Geom-
e y
A compu a ional uni e se objec Ucomp = (X, T,C,I) sa is ies:
1. Xis coun able con igu a ion se ;
2. T⊂X×Xis one-s ep upda e ela ion, local wi h ini e ou -deg ee;
3. C:X×X→[0,∞] is single-s ep cos , i (x, y)/∈T hen C(x, y) = ∞, o he wise
C(x, y)∈(0,∞), addi i e along pa hs;
3
4. I:X→Ris in o ma ion quali y o ask- ela ed sco e.
Complexi y dis ance de ined as
dcomp(x, y) = in
γ:x→yX
(u, )∈γ
C(u, ),
complexi y ball and olume as
BT(x0) = {x∈X:dcomp(x0, x)≤T}, Vx0(T) = |BT(x0)|.
Complexi y dimension de ined as
dimcomp(x0) = lim sup
T→∞
log Vx0(T)
log T,
i his limsup ini e, iew as local dimension.
Disc e e Ricci cu a u e κ(x, y) gi en h ough local ansi ion dis ibu ions mx, my
and Wasse s ein dis ance, in his pape we only use i s no a ion and ough p ope ies:
non-nega i e cu a u e ends owa d polynomial olume g ow h, nega i e cu a u e ends
owa d exponen ial olume g ow h.
2.2 Inpu Encoding and Geome ic Pe spec i e o Languages
Le Σ be ini e alphabe , Σ∗=Sn≥0Σnbe s ing se . Language L⊂Σ∗is a decision
p oblem. To discuss complexi y o Lin compu a ional uni e se, we need encoding amily.
De ini ion 2.1 (Inpu Encoding Family).An inpu encoding amily is map
ιn: Σn→X, n ∈N,
such ha o each w∈Σn,ιn(w) is ini ial con igu a ion in compu a ional uni e se
ep esen ing “inpu is w”.
We assume encoding amily sa is ies ollowing na u al condi ions:
1. Polynomial in e ibili y: he e exis cons an s c, k > 0, such ha decoding ιn(w)
back o whas compu a ion complexi y a mos cnk;
2. Locali y: encoding local modi ica ion w7→ w′co esponds o ini e local con igu a-
ion modi ica ion.
De ini ion 2.2 (Accep ance Region and Decision E olu ion).Fo language L⊂Σ∗,
de ine accep ance egion AL⊂Xas subse , such ha he e exis s upda e s a egy (de-
e mined by Tand possible con ol a iables) sa is ying:
I w∈L, hen s a ing om xin =ιn(w), he e exis s e mina ion con igu a ion
xacc ∈AL eachable wi hin ini e complexi y dis ance;
I w /∈L, hen s a ing om xin canno each any accep ance s a e, o can each
ejec ion s a e se RL⊂X AL.
When no dis inguishing explici ejec ion, can simply equi e sho es dis ance om
non-membe inpu o accep ance egion be +∞.
4
3 Geome ic Complexi y Func ions and Geome ic
Complexi y Classes
3.1 Geome ic Complexi y Func ion
De ini ion 3.1 (Geome ic Complexi y Func ion).Fo compu a ional uni e se Ucomp,
encoding amily {ιn}, and language L⊂Σ∗, de ine geome ic complexi y unc ion
TL(n) = sup
w∈Σn
in
x∈AL
dcompιn(w), x,
i o some wno accep ance pa h exis s hen TL(n) = +∞.
TL(n) ep esen s maximum complexi y dis ance needed o each some accep ance s a e
o all inpu s o leng h nunde op imal s a egy.
Unde uni ied ime scale in e p e a ion, TL(n) is uppe bound o “minimum physical
ime o wo s -case inpu ” unde ask L.
3.2 Geome ic Complexi y Classes
De ini ion 3.2 (Geome ic Complexi y Classes).In ixed compu a ional uni e se and
encoding amily, de ine:
Polynomial geome ic complexi y class
GC(poly) = nL⊂Σ∗:∃C, k > 0,∀n, TL(n)≤Cnko;
Subexponen ial geome ic complexi y class
GC(subexp) = nL:∀ε > 0,∃Cε>0,∀n, TL(n)≤Cε2εno;
Exponen ial geome ic complexi y class
GC(exp) = nL:∃C, c > 0,∀n, TL(n)≤C2cno.
Can u he de ine loga i hmic space geome ic classes, p obabilis ic geome ic classes,
e c., he e we ocus on geome ic adius co esponding o ime complexi y.
3.3 Equi alence wi h T adi ional Complexi y Classes
Unde p emise o “Tu ing–QCA–compu a ional uni e se polynomial equi alence”, we can
p o e:
P oposi ion 3.3 (Equi alence o Geome ic P Class and T adi ional P Class, Ou line).
Le Ucomp be compu a ional uni e se implemen ed by uni e sal de e minis ic Tu ing ma-
chine o e e sible CA/QCA, wi h na u al encoding amily {ιn}. Then he e exis con-
s an s c1, c2>0, such ha :
5
1. I L∈P, hen L∈GC(poly), wi h
TL(n)≤c1nk1
o some k1;
2. I L∈GC(poly), hen he e exis s cons an k2such ha L∈TIME(nk2).
The e o e, GC(poly) is equi alen o P a polynomial scale.
Simila ly, can gi e co esponding geome ic e sions o complexi y classes like EXP,
E, BQP. Since his pa highly simila o classical mul i-model equi alence, de ailed p oo s
le o Appendix C, only s uc u e gi en he e.
4 Volume G ow h, Complexi y Dimension, and Poly-
nomial Complexi y Cons ain s
This sec ion discusses how complexi y ball olume g ow h cons ains geome ic complex-
i y unc ion TL(n), he eby p o iding su icien condi ions o o m “geome ic condi ion
⇒polynomial complexi y”.
4.1 Volume G ow h and In o ma ion Encoding Capaci y
In ui i ely, numbe o di e en compu a ion ajec o ies and ou pu s a es ha can be
accommoda ed in complexi y ball BT(x0) is bounded abo e by Vx0(T): i wi hin adius T
he e a e only polynomial many di e en s a es, hen canno ealize exponen ially many
di e en ou pu pa e ns wi hin ha adius, o he wise pigeonhole p inciple would be
iola ed.
In language decision p oblems, we ca e abou abili y o dis inguish di e en inpu s: i
all inpu s o leng h nmap o inal s a e se wi hin BTL(n)(x0), hen |BTL(n)(x0)|mus be
in o ma ionally compa ible wi h |Σn|=|Σ|n, o he wise some inpu pai s will be con used.
P oposi ion 4.1 (Volume–Inpu Numbe Lowe Bound).Le encoding ιnbe injec i e,
and accep ance s a e se AL⊂Xno con use di e en inpu s (i.e., w1=w2⇒co e-
sponding inal s a es di e en ). Then o any n,
Vx0TL(n)≥ |Σ|n.
P oo . See Appendix A.1.
Thus i Vx0(T) g ows polynomially, hen TL(n) a leas Ω(log |Σ|n) = Ω(n); con e sely,
o gi en olume g ow h shape, can gi e cons ain s be ween uppe and lowe bounds o
TL(n).
4.2 Polynomial Volume G ow h ⇒Polynomial Complexi y
We ca e abou : i olume g ow h i sel polynomial, does i o ce complexi y unc ion
polynomial?
6
Theo em 4.2 (Complexi y Cons ain om Polynomial Volume G ow h).Suppose he e
exis basepoin x0and cons an s C0, k0>0, such ha o su icien ly la ge T,
Vx0(T)≤C0Tk0.
I language Lunde encoding ιnsa is ies:
1. Fo some cons an c > 0, all inpu w∈Σn inal s a es lie in subse o BcTL(n)(x0);
2. Di e en inpu inal s a es do no con use each o he ;
hen he e exis cons an s C1, k1>0, such ha
TL(n)≥C1n1/k0.
Simul aneously, om olume uppe bound and pigeonhole p inciple can de i e
TL(n)≥Ω|Σ|n/k0⇒no ealizable,
he e o e o ealizable languages, g ow h o TL(n)canno exceed ce ain polynomial
o de . Mo e p ecisely, unde na u al encoding and space locali y s uc u e, o la ge class
o languages ha e
TL(n) = Θn1/k0.
P oo idea see Appendix A.2.
In ui i ely, his heo em says: in compu a ional uni e se egion whe e olume g ow h
only polynomial, canno exis “essen ially exponen ially ha d” languages—exponen ial
explosion o complexi y equi es exponen ial expansion o olume as “ca ying space”.
5 Cu a u e, Exponen ial Volume Explosion, and Ex-
ponen ial Complexi y
This sec ion uses disc e e Ricci cu a u e and olume compa ison heo em o show ha in
local nega i e cu a u e egions he e necessa ily exis exponen ial complexi y languages,
he eby ob aining “nega i e cu a u e ↔exponen ial complexi y” geome ic–complexi y
connec ion.
5.1 Nega i e Cu a u e and Exponen ial Volume G ow h
P e ious complexi y geome y al eady p o ed: i he e exis K0>0 and T0>0, such
ha cu a u e o all adjacen poin pai s in BT0(x0) sa is ies κ(x, y)≤ −K0, hen he e
exis cons an s c, λ > 1 and in ege n0, such ha
Vx0(nT0)≥cλn, n ≥n0.
Tha is, exponen ial olume g ow h.
7
5.2 Cons uc ion o Exponen ial Complexi y Languages
In such egions, we can cons uc language amily {Lα}, such ha geome ic complexi y
unc ion TLα(n) o each Lαg ows a leas exponen ially. Cons uc ion idea as ollows:
1. Choose app op ia e encoding, such ha inpu s o leng h ncan be enume a ed as
|Σ|np e ixes;
2. In nega i e cu a u e egion selec amily o “b anching ee” ype subg aphs, whose
b anching ac o and laye numbe ma ch such ha di e en inpu ajec o ies
disc e ely co e exponen ially many poin s wi hin complexi y adius T;
3. Th ough accep ance egion design, o ce di e en inpu s o walk owa d di e en
b anching lea es, and hese lea es mu ually sepa a ed by a leas some cons an ,
ensu ing no con usion;
4. Use olume lowe bound and pa h s uc u e o p o e: wi hin adius smalle han
some exponen ial unc ion, canno assign di e en lea es o all inpu s, he eby
de i ing complexi y lowe bound.
Theo em 5.1 (Exponen ial Complexi y Languages in Nega i e Cu a u e Regions).Un-
de abo e nega i e cu a u e assump ions, he e exis language amily {Lα}and encoding
amily {ια
n}, such ha o each α he e exis s cons an cα>0, sa is ying
TLα(n)≥2cαn o su icien ly la ge n.
P oo ou line see Appendix B.
This esul does no say “all nega i e cu a u e egions co espond o NP–ha d”, bu
a he shows geome ically he e exis s “embeddabili y” o exponen ial complexi y, i.e.,
nega i e cu a u e p o ides space o exponen ially many geodesic b anches.
6 Quan um Case: QCA Uni e se and Geome ic Up-
pe Bound o BQP
This sec ion b ie ly discusses quan um compu a ion case, gi ing geome ic uppe bound
o BQP class in QCA uni e se.
6.1 QCA Uni e se and Con ol Mani old
In e e sible quan um cellula au oma on uni e se, global e olu ion gi en by uni a y
ope a o U, whose local s uc u e and uni ied ime scale densi y κ(ω;θ) de ine amily o
con ol pa ame e s θ∈ M and me ic Gab(θ). Quan um ci cui model can be iewed as
special QCA, ealizing BQP class languages.
Fo quan um algo i hms, we can iew hei con ol pa h θ( ) as cu e on (M, G), wi h
leng h
LG[θ] = ZT
0qGab(θ( )) ˙
θa˙
θbd
co esponding o o al “physical ime” o ga e numbe equi alen o quan um com-
pu a ion.
8
6.2 Geome ic Uppe Bound o BQP
Unde s anda d model equi alence and app op ia e egula i y, can p o e:
P oposi ion 6.1 (Geome ic Uppe Bound o BQP).Fo any language L∈BQP,
he e exis QCA uni e se and con ol mani old (M, G)as well as encoding amily {ιn},
such ha i s geome ic complexi y unc ion TL(n)has polynomial equi alence wi h con ol
geodesic leng h:
TL(n)≤C1nk1⇐⇒ ∃ θn( )such ha LG[θn]≤C2nk2,
whe e C1, C2, k1, k2a e cons an s, and classical geome ic complexi y class GC(poly)
and BQP sha e polynomial uppe bound in sense o geodesic leng h on con ol mani old.
In his sense, quan um ad an age mainly mani es ed in exploi ing Hilbe space s uc-
u e and phase in e e ence, allowing “pa allel explo a ion” o mo e pa hs a same ge-
ome ic leng h, a he han b eaking geome ic uppe bound induced by uni ied ime
scale.
De ailed p oo elies on ga e se uni e sali y and s anda d cons uc ion o QCA sim-
ula ing quan um ci cui s, omi ed he e.
7 Conclusion
This pape cons uc s wi hin compu a ional uni e se and uni ied ime scale–complexi y
geome y amewo k a geome ic complexi y hie a chy heo y: h ough complexi y dis-
ance, olume g ow h, cu a u e, and con ol mani old geodesic s uc u e, we gi e geo-
me ic cha ac e iza ions o adi ional complexi y classes.
We in oduce geome ic complexi y unc ion TL(n) and geome ic complexi y classes
GC(poly), GC(exp), e c., and unde “Tu ing–QCA–compu a ional uni e se equi alence”
assump ion p o e polynomial scale equi alence wi h adi ional complexi y classes like P,
EXP. Th ough analyzing complexi y ball olume g ow h and complexi y dimension, we
p o e: in egions wi h polynomial olume g ow h, he e exis no geome ically essen ially
exponen ially ha d p oblems, while in egions whe e nega i e cu a u e leads o expo-
nen ial olume expansion, we can cons uc exponen ial complexi y language amilies.
Addi ionally, his pape b ie ly discusses BQP class in quan um case, poin ing ou
ha unde uni ied ime scale and con ol mani old me ic, geome ic complexi y o BQP
languages s ill bounded by polynomial uppe bound, wi h quan um ad an age mani es ed
in exploi ing Hilbe space in e e ence s uc u e, a he han b eaking geome ic uppe
limi .
These esul s p o ide ounda ion o se e al subsequen di ec ions: o example, “com-
plexi y phase ansi ions” can be iewed as s a i ica ion changes o complexi y classes
when geome ic s uc u es ( olume g ow h and cu a u e) unde go mu a ions; “capabili y–
isk on ie ” can be desc ibed as geome ic eachable egion bounda y when simul ane-
ously conside ing ask in o ma ion gain and sa e y cons ain s on complexi y geome y;
while mul i-obse e consensus geome y can use complexi y ho izons and olume g ow h
o cha ac e ize limi a ions o “collec i ely eachable knowledge space”.
9
