Disc e e Complexi y Geome y o Compu a ional
Uni e ses:
Me ics, Volume G ow h, and Local Cu a u e on
Con igu a ion G aphs
Haobo Ma1Wenlin Zhang2
1Independen Resea che
2Na ional Uni e si y o Singapo e
No embe 24, 2025
Abs ac
In he p e ious wo k, we axioma ized he “compu a ional uni e se” as a quad u-
ple Ucomp = (X, T,C,I) wi h con igu a ion space, one-s ep upda e ela ion, single-
s ep cos , and in o ma ion quali y unc ion. Building on his ounda ion, we de-
elop a “disc e e complexi y geome y” amewo k ha uses pu ely disc e e g aph-
heo e ic and me ic s uc u es o cha ac e ize ime complexi y o compu a ional
p ocesses, “geome ic di icul y” o p oblems, and he s uc u e o eachable do-
mains and ho izons unde ini e esou ces.
Fi s , we associa e each compu a ional uni e se wi h a weigh ed di ec ed g aph
Gcomp = (X, E, w), whe e edge se E=Tand edge weigh s w(x, y) = C(x, y). Un-
de app op ia e ini eness and gene alized e e sibili y assump ions, his s uc u e
induces a gene alized me ic d:X×X→[0,∞], whose sho es pa h alues a e
equi alen o a physicalized e sion o disc e e ime complexi y. We de ine com-
plexi y balls BT(x0) = {x:d(x0, x)≤T}and complexi y olume g ow h unc ions
Vx0(T) = |BT(x0)|, in oducing a “complexi y dimension” dimcomp(x0) measu ing
g ow h o de o complexi y nea a gi en s a ing poin .
Second, we in oduce a disc e e Ricci cu a u e κ(x, y) based on ansi ion
p obabili ies and i s -o de Wasse s ein dis ance on weigh ed g aphs, quali a i ely
cha ac e izing “di e gence” o “con ac ion” endencies o complex pa hs in lo-
cal egions. We p o e ha unde na u al assump ions, nega i e cu a u e egions
co espond o exponen ial olume g ow h o complexi y balls, while non-nega i e
cu a u e egions co espond o polynomial o sub-exponen ial g ow h, es ablishing
a quali a i e connec ion be ween cu a u e and p oblem di icul y.
Thi d, we iew he amily o eachable domains {BT(x0)}T >0as “complexi y
ho izons” e ol ing wi h esou ce budge T, cha ac e izing complexi y phase an-
si ions h ough simple homological and connec i i y indica o s: when Tc osses
ce ain c i ical alues, he numbe o connec ed componen s, undamen al g oup,
o i s homology g oup o eachable domains unde goes mu a ions, co esponding
o algo i hms “suddenly opening new ou es” in complexi y geome y.
Finally, assuming he compu a ional uni e se a ises om a physical implemen-
a ion con olled by a uni ied ime scale κ(ω), we discuss how a amily o com-
plexi y g aphs con e ges o a Riemannian mani old (M, G) unde mesh e inemen
1
limi s, such ha disc e e complexi y dis ance dapp oxima es geodesic dis ance
induced by Ga la ge scales, p o iding se e al igo ous con e gence heo ems in
low-dimensional cases.
As he second wo k in he “Compu a ional Uni e se Theo y” se ies, his pape
p o ides he i s b idge om ully disc e e compu a ional s uc u es o geome ized
complexi y, laying ounda ions o subsequen wo k uni ying in o ma ion geome y,
ime scales, and ca ego y equi alence be ween physical and compu a ional uni-
e ses.
Keywo ds: Compu a ional Uni e se, Complexi y Geome y, Weigh ed G aphs, Ricci
Cu a u e, Volume G ow h, Complexi y Ho izon, Uni ied Time Scale
MSC 2020: 68Q15, 53C23, 68Q17, 05C81, 68Q12
1 In oduc ion
A he in e sec ion o compu a ional heo y and physics, iewing “ he uni e se as com-
pu a ion” has become an impo an app oach. I we accep he se ing om he p e ious
wo k: he en i e uni e se can be abs ac ed as a disc e e dynamical sys em Ucomp =
(X, T,C,I) wi h ini e in o ma ion densi y, local upda es, and uni ied ime scale, hen a
na u al ques ion a ises: can his disc e e s uc u e possess geome ic concep s simila o
Riemannian geome y, such as “cu a u e,” “ olume g ow h,” and “ho izons,” he eby
unde s anding compu a ional complexi y and p oblem di icul y in geome ic e ms?
T adi ional complexi y heo y o en uses s ep coun s o ga e numbe s as complexi y
measu es, wi hou conside ing geome ic ela ionships be ween di e en compu a ional
pa hs. On he o he hand, de elopmen s in g aph geome y and disc e e Ricci cu a u e
show ha cons uc ing con inuous geome y-like s uc u es on weigh ed g aphs is easible.
This pape sys ema ically me ges hese wo h eads wi hin he “compu a ional uni e se”
axioma ic amewo k in o a uni ied “disc e e complexi y geome y” heo y.
The main con ibu ions o his pape can be summa ized as ollows:
1. P o ide a uni ied cons uc ion om compu a ional uni e se Ucomp o complexi y
g aph Gcomp and complexi y dis ance d, p o ing i is a gene alized me ic unde
na u al condi ions, and de ining complexi y balls, complexi y olume, and com-
plexi y dimension.
2. In oduce Ricci cu a u e κ(x, y) based on disc e e ansi ion dis ibu ions and
Wasse s ein dis ance on complexi y g aphs, p o ing quali a i e connec ions be ween
i s sign and complexi y olume g ow h ypes.
3. Taking eachable domain amilies BT(x0) as objec s, in oduce concep s o complex-
i y ho izons and complexi y phase ansi ions, desc ibing “ opological ansi ions”
o eachable domains a ying wi h esou ce budge Tusing simple algeb aic opo-
logical in a ian s.
4. Unde he assump ion o a uni ied ime scale, p o ide condi ions o a amily o
complexi y g aphs o con e ge o a mani old (M, G) unde mesh e inemen limi s,
p o ing consis ency be ween disc e e complexi y dis ance and con inuous geodesic
dis ance in low-dimensional cases.
2
The s uc u e is as ollows: Sec ion 2 e iews compu a ional uni e se axioms and con-
s uc s complexi y g aphs and dis ances. Sec ion 3 s udies olume g ow h and complexi y
dimension. Sec ion 4 in oduces disc e e Ricci cu a u e and discusses i s ela ionship
wi h complexi y g ow h. Sec ion 5 discusses complexi y ho izons and phase ansi ion
s uc u es. Sec ion 6 discusses mani old limi s and consis ency wi h uni ied ime scale.
Appendices p o ide de ailed p oo s o main p oposi ions and heo ems.
2 F om Compu a ional Uni e se o Complexi y G aph
and Me ic
This sec ion p o ides mo e e ined cons uc ion and analysis o complexi y g aphs and
complexi y dis ances based on de ini ions om he p e ious wo k.
2.1 Basic Re iew o Compu a ional Uni e se
Recall he de ini ion o compu a ional uni e se.
De ini ion 2.1 (Compu a ional Uni e se Recap).A compu a ional uni e se objec is a
quad uple Ucomp = (X, T,C,I), whe e:
1. Xis a coun able con igu a ion se ;
2. T⊂X×Xis he one-s ep upda e ela ion;
3. C:X×X→[0,∞] is he single-s ep cos sa is ying: i (x, y)/∈T, hen C(x, y) = ∞;
i (x, y)∈T, hen C(x, y)∈(0,∞);
4. I:X→Ris he in o ma ion quali y unc ion.
Sa is ying axioms o ini e in o ma ion densi y, local upda e, gene alized e e sibili y,
and cos addi i i y.
Fo any ini e pa h γ= (x0, . . . , xn) sa is ying (xk, xk+1)∈T, de ine pa h cos
C(γ) =
n−1
X
k=0
C(xk, xk+1)
and de ine complexi y dis ance
d(x, y) = in
γ:x→y
C(γ)
whe e γ anges o e all ini e pa hs om x o y.
The p e ious wo k p o ed ha unde app op ia e eachabili y and symme y con-
di ions, dis a gene alized me ic. This sec ion uses his as basis o de ine complexi y
g aphs.
3
2.2 De ini ion o Complexi y G aph
De ini ion 2.2 (Complexi y G aph).Gi en compu a ional uni e se Ucomp = (X, T,C,I),
i s complexi y g aph is a weigh ed di ec ed g aph Gcomp = (X, E, w), whe e:
1. Ve ex se is X;
2. Di ec ed edge se is E=T;
3. Edge weigh w:E→(0,∞] is de ined as w(x, y) = C(x, y).
I an undi ec ed g aph s uc u e is needed, de ine symme ic edge se
Esym ={{x, y}: (x, y)∈Eo (y, x)∈E}
wi h edge weigh s
wsym({x, y}) = min{C(x, y),C(y, x)}
De ini ion 2.3 (Fini e Region o Complexi y Dis ance).De ine he eachable subse
X in ={x∈X:d(x0, x)<∞}
whe e x0∈Xis a chosen e e ence con igu a ion. In his pape , we o en es ic discus-
sion o X in when unambiguous.
Resul s om he p e ious wo k immedia ely gi e he ollowing p oposi ion.
P oposi ion 2.4 (Me ic P ope ies o Complexi y Dis ance).On X in, complexi y dis-
ance dsa is ies:
1. d(x, x)=0;
2. d(x, y)≥0, and d(x, y)=0implies x=y;
3. d(x, z)≤d(x, y) + d(y, z).
I Tis e e sible on X in and cos s a e symme ic unde edge e e sal, hen d(x, y) =
d(y, x), making (X in, d)a me ic space.
P oo in Appendix A.1.
2.3 Complexi y Balls and Volume Func ions
De ini ion 2.5 (Complexi y Ball and Volume).Fo x0∈X in and T > 0, de ine he
complexi y ball
BT(x0) = {x∈X in :d(x0, x)≤T}
I s olume (by poin coun ing) is
Vx0(T) = |BT(x0)| ∈ N∪ {∞}
P oposi ion 2.6 (Mono onici y and Subaddi i i y).1. Fo any T1< T2, we ha e
BT1(x0)⊆BT2(x0), hus Vx0(T1)≤Vx0(T2);
2. I he e exis s cons an C > 0such ha o all T1, T2>0,
Vx0(T1+T2)≤C Vx0(T1)Vx0(T2)
hen log Vx0(T)is subaddi i e.
P oo in Appendix A.2. The second condi ion na u ally holds in many local g aphs,
p o iding basis o de ining complexi y g ow h exponen s.
4
3 Volume G ow h and Complexi y Dimension
The g ow h a e o complexi y ball olume is he na u al objec o cha ac e izing “local
complexi y dimension o compu a ional uni e se.” This sec ion p o ides basic de ini ions
and p ope ies.
3.1 De ini ion o Complexi y Dimension
De ini ion 3.1 (Uppe and Lowe Complexi y Dimension).Fo a gi en s a ing poin
x0∈X in, de ine he uppe complexi y dimension as
dimcomp(x0) = lim sup
T→∞
log Vx0(T)
log T
The lowe complexi y dimension is
dimcomp(x0) = lim in
T→∞
log Vx0(T)
log T
I he wo a e equal, hei common alue is called he complexi y dimension, deno ed
dimcomp(x0).
In ui i ely, dimcomp(x0) desc ibes he polynomial o de o g ow h o eachable con ig-
u a ions om x0as complexi y budge Tinc eases. I dimcomp(x0) = ∞, hen eachable
domain olume g ows a leas supe -polynomially.
3.2 Rela ionship wi h G aph S uc u e
Fo undi ec ed local g aphs, olume g ow h o de is closely ela ed o i s “g aph dimen-
sion.” In complexi y g aphs, we can ob ain a simila esul .
P oposi ion 3.2 (Polynomial G ow h in Bounded Deg ee Case).Assume he undi ec ed
symme ic e sion (X in, Esym)o he complexi y g aph has bounded deg ee, i.e., he e
exis s D > 0such ha o all x∈X in,deg(x)≤D. I addi ionally single-s ep cos s a e
bounded in some in e al, i.e., he e exis cons an s 0< cmin ≤cmax <∞such ha o
all edges {x, y} ∈ Esym,
cmin ≤wsym({x, y})≤cmax
hen he e exis cons an s C1, C2>0and in ege d∗≥0such ha o su icien ly la ge
T,
C1Td∗≤Vx0(T)≤C2Td∗
In pa icula , dimcomp(x0) = d∗.
P oo in Appendix A.3, using linea ela ionship be ween edge coun s and s ep coun s
o educe complexi y balls o s ep balls, and u ilizing olume g ow h es ima es o
bounded-deg ee g aphs.
P oposi ion 3.3 (Exponen ial G ow h and Supe -Polynomial Complexi y).I he e exis
cons an s λ > 1and T0>0such ha o all n∈N,
Vx0(nT0)≥λn
hen dimcomp(x0) = ∞.
In o he wo ds, exponen ial g ow h o complexi y ball olume implies in ini e complex-
i y dimension.
5
P oo in Appendix A.4.
These esul s show: when complexi y dimension is ini e, g ow h o complexi y wi h
budge Thas some “dimension con ollabili y”; while exponen ial g ow h means local
“explosion” in complexi y geome y, co esponding o highly in ac able sea ch spaces.
4 Disc e e Ricci Cu a u e and P oblem Di icul y
In me ic spaces, he sign o Ricci cu a u e is closely ela ed o olume g ow h and
geodesic de ia ion. This sec ion in oduces a disc e e Ricci cu a u e on complexi y
g aphs, cha ac e izing di e gence o con ac ion o complex pa hs in local egions, and
discusses quali a i e connec ions wi h complexi y olume g ow h.
4.1 Disc e e Ricci Cu a u e Based on T ansi ion Dis ibu ions
We adop coa se Ricci cu a u e based on i s -o de Wasse s ein dis ance, adap ed o
di ec ed weigh ed g aphs.
De ini ion 4.1 (Local One-S ep T ansi ion Dis ibu ion).On complexi y g aph Gcomp =
(X, E, w), de ine he local one-s ep ansi ion dis ibu ion om xas
mx(y) = a(x, y)
Pza(x, z)
whe e
a(x, y) = (exp(−λw(x, y)),(x, y)∈E,
0,o he wise,
and λ > 0 is a ixed scale pa ame e .
This is a andom walk ke nel biased owa d “low-cos edges.”
De ini ion 4.2 (Ricci Cu a u e on Complexi y G aph).Fo x=y, de ine he disc e e
Ricci cu a u e om x o yas
κ(x, y)=1−W1(mx, my)
d(x, y)
whe e W1is he i s -o de Wasse s ein dis ance ela i e o complexi y dis ance d.
When he a e age displacemen o mass be ween mxand myunde dis less han
d(x, y), we ha e κ(x, y)>0; con e sely i a e age displacemen exceeds d(x, y), hen
κ(x, y)<0.
4.2 Cu a u e and Geodesic Di e gence
In classical me ic spaces, Ricci cu a u e lowe bounds con ol “a e age con ac ion”
be ween geodesics. In ou complexi y g aphs, we can p o e a disc e e analog.
Theo em 4.3 (Cu a u e Lowe Bound and Complexi y Dis ance Con ac ion).Suppose
he e exis s cons an K∈Rsuch ha o all adjacen e ices x, y (i.e., d(x, y)bounded),
κ(x, y)≥K. Then o any wo ini ial dis ibu ions µ, ν, hei dis ibu ions µP, νP a e
one andom walk (whe e Pis he ansi ion ope a o ) sa is y
W1(µP, νP)≤(1 −K)W1(µ, ν)
6
In pa icula , when K > 0, Wasse s ein dis ance decays exponen ially; when K < 0,
dis ance expands exponen ially.
P oo in Appendix B.1. The p oo uses he de ini ion o κ(x, y) and disc e e Kan-
o o ich duali y o es ima e beha io o Di ac dis ibu ions, ex ending o gene al dis i-
bu ions.
4.3 Cu a u e and Complexi y Volume G ow h
The e exis quali a i e connec ions be ween cu a u e lowe bounds and olume g ow h.
Theo em 4.4 (Polynomial G ow h Unde Non-Nega i e Cu a u e).Assume he com-
plexi y g aph is a locally ini e di ec ed g aph wi h bounded symme ic e sion deg ee, and
he e exis s K≥0such ha o all adjacen x, y,κ(x, y)≥K. Then he e exis cons an s
C, d∗and T0>0such ha o all T≥T0,
Vx0(T)≤CTd∗
In pa icula , dimcomp(x0)≤d∗.
Theo em 4.5 (Exponen ial G ow h Unde S ic ly Nega i e Cu a u e).Assume he e
exis K0>0and δ > 0such ha o all poin pai s sa is ying d(x, y)≤δ,κ(x, y)≤ −K0.
Then he e exis cons an s c, λ > 1and T0>0such ha o all n∈N,
Vx0(nT0)≥cλn
These wo heo ems show ha non-nega i e cu a u e con ols complexi y olume
g ow h polynomially, while local s ic ly nega i e cu a u e leads o exponen ial explosion
o complexi y space. P oo ideas bo ow om Bishop–G omo compa ison heo y and
G omo hype bolic space olume g ow h es ima es in con inuous cases, bu pe o med
en i ely on disc e e g aphs; see Appendices B.2 and B.3.
5 Reachable Domains, Complexi y Ho izons, and Phase
T ansi ions
This sec ion discusses opological e olu ion o eachable domain amilies {BT(x0)}as
complexi y budge Tinc eases, cha ac e izing complexi y phase ansi ions using simple
algeb aic opological indica o s.
5.1 De ini ion o Complexi y Ho izon
De ini ion 5.1 (Complexi y Ho izon).Fo ixed s a ing poin x0, call a sequence {T(k)
c}k∈K⊂
(0,∞) a complexi y ho izon poin amily i o each T(k)
c he e exis s a opological in a i-
an I(e.g., numbe o connec ed componen s, i s Be i numbe , undamen al g oup
o de ) such ha when Tc osses a neighbo hood o T(k)
c,I(BT(x0)) unde goes a jump.
In p ac ice, he simples choices a e numbe o connec ed componen s and i s Be i
numbe .
7
De ini ion 5.2 (Connec i i y Phase T ansi ion).Le cc(T) deno e he numbe o con-
nec ed componen s o BT(x0) in he symme ic g aph. I he e exis s Tcsuch ha
lim
ε↓0cc(Tc−ε)>lim
ε↓0cc(Tc+ε)
hen Tcis called a connec i i y complexi y phase ansi ion poin .
De ini ion 5.3 (Cycle S uc u e Phase T ansi ion).Le b1(T) deno e he i s Be i
numbe (numbe o cycles) o BT(x0). I he e exis s Tcsuch ha b1(Tc−ε)=b1(Tc+ε)
o any su icien ly small ε > 0, hen Tcis called a cycle s uc u e complexi y phase
ansi ion poin .
5.2 Phase T ansi ions and Cu a u e Compa ison
In s ongly nega i e cu a u e egions, complexi y balls o en apidly include la ge num-
be s o “new pa hs,” leading o apid cycle numbe g ow h; while in non-nega i e cu -
a u e egions, complexi y ball expansion is ela i ely mild, wi h cycle s uc u e g ow h
supp essed.
We ha e he ollowing quali a i e p oposi ions.
P oposi ion 5.4 (Cycle G ow h Cons ain Unde Local Non-Nega i e Cu a u e).As-
sume he e exis s R > 0such ha wi hin BR(x0), all adjacen poin pai s ha e cu a u e
sa is ying κ(x, y)≥0, and he g aph has bounded deg ee. Then he e exis cons an s
C1, C2>0such ha o T≤R,
b1(T)≤C1Vx0(T) + C2
In pa icula , i Vx0(T)is polynomially bounded, hen b1(T)also g ows a mos poly-
nomially.
P oo in Appendix C.1.
P oposi ion 5.5 (Rapid Cycle Appea ance Unde Local Nega i e Cu a u e).I in
some annula laye A=BT2(x0) BT1(x0), he e exis many poin pai s x, y sa is ying
κ(x, y)≤ −K0wi h bounded d(x, y), hen as Tinc eases om T1 o T2, he e exis s a
leas one cycle s uc u e phase ansi ion poin Tc∈(T1, T2).
P oo in Appendix C.2.
These esul s show ha cu a u e no only con ols olume g ow h bu also de e mines
appea ance o complexi y ho izons and “s uc u al phase ansi ions” o some ex en .
This p o ides geome ic in e p e a ion o algo i hms expe iencing “sudden insigh s” o
“s uc u al leaps” when inc easing esou ces.
6 Mani old Limi s and Uni ied Time Scale
This sec ion discusses how complexi y g aphs con e ge o a Riemannian mani old when
compu a ional uni e ses ha e good con inuous limi s, how disc e e complexi y dis ances
app oxima e con inuous geodesic dis ances, and discusses consis ency be ween uni ied
ime scale κ(ω) and complexi y me ics.
8
6.1 Mani old Limi s o Complexi y G aphs
Conside a amily o compu a ional uni e ses {U(h)
comp}h>0, whe e hdeno es disc e e scale
(e.g., la ice spacing, con ol pa ame e s ep), co esponding o complexi y g aphs G(h)
comp =
(X(h), E(h), w(h)) and dis ances d(h).
De ini ion 6.1 (G omo –Hausdo Con e gence).I he e exis Riemannian mani old
(M, G) wi h poin θ0∈ M, and embedding maps Φh:X(h)→ M, such ha o any
bounded R > 0:
1. Φh(B(h)
R(x(h)
0)) Hausdo con e ges o BR(θ0) in M;
2. Fo all x, y ∈B(h)
R(x(h)
0),
lim
h→0dG(Φh(x),Φh(y)) = lim
h→0d(h)(x, y)
hen he complexi y g aph amily (X(h), d(h)) is said o con e ge locally in G omo –Hausdo
sense o (M, dG).
He e dGis he geodesic dis ance induced by Riemannian me ic G.
Theo em 6.2 (Rigo ous Con e gence in One Dimension).Suppose o each h > 0, com-
plexi y g aph G(h)
comp has e ices X(h)=hZ∩[−L, L], di ec ed edges E(h)={(x, x ±h)},
edge weigh s w(h)(x, x ±h) = c(x)h, whe e c: [−L, L]→(cmin, cmax)is a con inu-
ous posi i e unc ion. Then as h→0, he me ic space (X(h), d(h))con e ges in G o-
mo –Hausdo sense o he Riemannian mani old (M, G)on in e al [−L, L], whe e
M= [−L, L]and he me ic is
G(θ) = c(θ)2dθ2
The geodesic dis ance is
dG(θ1, θ2) = Zθ2
θ1
c(θ) dθ
and o any θ1, θ2∈[−L, L],
lim
h→0d(h)(θ(h)
1, θ(h)
2) = dG(θ1, θ2)
whe e θ(h)∈X(h)a e nea es poin samples.
P oo in Appendix D.1. This is a igo ous e sion o “disc e e cos sum →con inuous
pa h in eg al” in one dimension.
Highe -dimensional cases can be ob ained h ough simila cons uc ions. Unde ap-
p op ia e egula i y and locali y assump ions, a amily o complexi y g aphs can con e ge
o some mani old (M, G), whe e Gis de e mined by second-o de s uc u e o local cos
unc ion amilies.
9
