Discrete Complexity Geometry of Computational Universes:\\ Metrics, Volume Growth, and Local Curvature on Configuration Graphs

Discrete Complexity Geometry of Computational Universes: Metrics, Volume Growth, and Local Curvature on Configuration Graphs Haobo Ma1Wenlin Zhang2 1Independent Researcher 2National University of Singapore November 24, 2025 Abstract In the previous work, we axiomatized the “computational universe” as a quadruple Ucomp = (X, T,C,I) with configuration space, one-step update relation, singlestep cost, and information quality function. Building on this foundation, we develop a “discrete complexity geometry” framework that uses purely discrete graphtheoretic and metric structures to characterize time complexity of computational processes, “geometric difficulty” of problems, and the structure of reachable domains and horizons under finite resources. First, we associate each computational universe with a weighted directed graph Gcomp = (X, E, w), where edge set E=Tand edge weights w(x, y) = C(x, y). Under appropriate finiteness and generalized reversibility assumptions, this structure induces a generalized metric d:X×X→[0,∞], whose shortest path values are equivalent to a physicalized version of discrete time complexity. We define complexity balls BT(x0) = {x:d(x0, x)≤T}and complexity volume growth functions Vx0(T) = |BT(x0)|, introducing a “complexity dimension” dimcomp(x0) measuring growth order of complexity near a given starting point. Second, we introduce a discrete Ricci curvature κ(x, y) based on transition probabilities and first-order Wasserstein distance on weighted graphs, qualitatively characterizing “divergence” or “contraction” tendencies of complex paths in local regions. We prove that under natural assumptions, negative curvature regions correspond to exponential volume growth of complexity balls, while non-negative curvature regions correspond to polynomial or sub-exponential growth, establishing a qualitative connection between curvature and problem difficulty. Third, we view the family of reachable domains {BT(x0)}T >0as “complexity horizons” evolving with resource budget T, characterizing complexity phase transitions through simple homological and connectivity indicators: when Tcrosses certain critical values, the number of connected components, fundamental group, or first homology group of reachable domains undergoes mutations, corresponding to algorithms “suddenly opening new routes” in complexity geometry. Finally, assuming the computational universe arises from a physical implementation controlled by a unified time scale κ(ω), we discuss how a family of complexity graphs converges to a Riemannian manifold (M, G) under mesh refinement 1 limits, such that discrete complexity distance dapproximates geodesic distance induced by Gat large scales, providing several rigorous convergence theorems in low-dimensional cases. As the second work in the “Computational Universe Theory” series, this paper provides the first bridge from fully discrete computational structures to geometrized complexity, laying foundations for subsequent work unifying information geometry, time scales, and category equivalence between physical and computational universes. Keywords: Computational Universe, Complexity Geometry, Weighted Graphs, Ricci Curvature, Volume Growth, Complexity Horizon, Unified Time Scale MSC 2020: 68Q15, 53C23, 68Q17, 05C81, 68Q12 1 Introduction At the intersection of computational theory and physics, viewing “the universe as computation” has become an important approach. If we accept the setting from the previous work: the entire universe can be abstracted as a discrete dynamical system Ucomp = (X, T,C,I) with finite information density, local updates, and unified time scale, then a natural question arises: can this discrete structure possess geometric concepts similar to Riemannian geometry, such as “curvature,” “volume growth,” and “horizons,” thereby understanding computational complexity and problem difficulty in geometric terms? Traditional complexity theory often uses step counts or gate numbers as complexity measures, without considering geometric relationships between different computational paths. On the other hand, developments in graph geometry and discrete Ricci curvature show that constructing continuous geometry-like structures on weighted graphs is feasible. This paper systematically merges these two threads within the “computational universe” axiomatic framework into a unified “discrete complexity geometry” theory. The main contributions of this paper can be summarized as follows: 1. Provide a unified construction from computational universe Ucomp to complexity graph Gcomp and complexity distance d, proving it is a generalized metric under natural conditions, and defining complexity balls, complexity volume, and complexity dimension. 2. Introduce Ricci curvature κ(x, y) based on discrete transition distributions and Wasserstein distance on complexity graphs, proving qualitative connections between its sign and complexity volume growth types. 3. Taking reachable domain families BT(x0) as objects, introduce concepts of complexity horizons and complexity phase transitions, describing “topological transitions” of reachable domains varying with resource budget Tusing simple algebraic topological invariants. 4. Under the assumption of a unified time scale, provide conditions for a family of complexity graphs to converge to a manifold (M, G) under mesh refinement limits, proving consistency between discrete complexity distance and continuous geodesic distance in low-dimensional cases. 2 The structure is as follows: Section 2 reviews computational universe axioms and constructs complexity graphs and distances. Section 3 studies volume growth and complexity dimension. Section 4 introduces discrete Ricci curvature and discusses its relationship with complexity growth. Section 5 discusses complexity horizons and phase transition structures. Section 6 discusses manifold limits and consistency with unified time scale. Appendices provide detailed proofs of main propositions and theorems. 2 From Computational Universe to Complexity Graph and Metric This section provides more refined construction and analysis of complexity graphs and complexity distances based on definitions from the previous work. 2.1 Basic Review of Computational Universe Recall the definition of computational universe. Definition 2.1 (Computational Universe Recap).A computational universe object is a quadruple Ucomp = (X, T,C,I), where: 1. Xis a countable configuration set; 2. T⊂X×Xis the one-step update relation; 3. C:X×X→[0,∞] is the single-step cost satisfying: if (x, y)/∈T, then C(x, y) = ∞; if (x, y)∈T, then C(x, y)∈(0,∞); 4. I:X→Ris the information quality function. Satisfying axioms of finite information density, local update, generalized reversibility, and cost additivity. For any finite path γ= (x0, . . . , xn) satisfying (xk, xk+1)∈T, define path cost C(γ) = n−1 X k=0 C(xk, xk+1) and define complexity distance d(x, y) = inf γ:x→y C(γ) where γranges over all finite paths from xto y. The previous work proved that under appropriate reachability and symmetry conditions, dis a generalized metric. This section uses this as basis to define complexity graphs. 3 2.2 Definition of Complexity Graph Definition 2.2 (Complexity Graph).Given computational universe Ucomp = (X, T,C,I), its complexity graph is a weighted directed graph Gcomp = (X, E, w), where: 1. Vertex set is X; 2. Directed edge set is E=T; 3. Edge weight w:E→(0,∞] is defined as w(x, y) = C(x, y). If an undirected graph structure is needed, define symmetric edge set Esym ={{x, y}: (x, y)∈Eor (y, x)∈E} with edge weights wsym({x, y}) = min{C(x, y),C(y, x)} Definition 2.3 (Finite Region of Complexity Distance).Define the reachable subset Xfin ={x∈X:d(x0, x)<∞} where x0∈Xis a chosen reference configuration. In this paper, we often restrict discussion to Xfin when unambiguous. Results from the previous work immediately give the following proposition. Proposition 2.4 (Metric Properties of Complexity Distance).On Xfin, complexity distance dsatisfies: 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). If Tis reversible on Xfin and costs are symmetric under edge reversal, then d(x, y) = d(y, x), making (Xfin, d)a metric space. Proof in Appendix A.1. 2.3 Complexity Balls and Volume Functions Definition 2.5 (Complexity Ball and Volume).For x0∈Xfin and T > 0, define the complexity ball BT(x0) = {x∈Xfin :d(x0, x)≤T} Its volume (by point counting) is Vx0(T) = |BT(x0)| ∈ N∪ {∞} Proposition 2.6 (Monotonicity and Subadditivity).1. For any T1< T2, we have BT1(x0)⊆BT2(x0), thus Vx0(T1)≤Vx0(T2); 2. If there exists constant C > 0such that for all T1, T2>0, Vx0(T1+T2)≤C Vx0(T1)Vx0(T2) then log Vx0(T)is subadditive. Proof in Appendix A.2. The second condition naturally holds in many local graphs, providing basis for defining complexity growth exponents. 4 3 Volume Growth and Complexity Dimension The growth rate of complexity ball volume is the natural object for characterizing “local complexity dimension of computational universe.” This section provides basic definitions and properties. 3.1 Definition of Complexity Dimension Definition 3.1 (Upper and Lower Complexity Dimension).For a given starting point x0∈Xfin, define the upper complexity dimension as dimcomp(x0) = lim sup T→∞ log Vx0(T) log T The lower complexity dimension is dimcomp(x0) = lim inf T→∞ log Vx0(T) log T If the two are equal, their common value is called the complexity dimension, denoted dimcomp(x0). Intuitively, dimcomp(x0) describes the polynomial order of growth of reachable configurations from x0as complexity budget Tincreases. If dimcomp(x0) = ∞, then reachable domain volume grows at least super-polynomially. 3.2 Relationship with Graph Structure For undirected local graphs, volume growth order is closely related to its “graph dimension.” In complexity graphs, we can obtain a similar result. Proposition 3.2 (Polynomial Growth in Bounded Degree Case).Assume the undirected symmetric version (Xfin, Esym)of the complexity graph has bounded degree, i.e., there exists D > 0such that for all x∈Xfin,deg(x)≤D. If additionally single-step costs are bounded in some interval, i.e., there exist constants 0< cmin ≤cmax <∞such that for all edges {x, y} ∈ Esym, cmin ≤wsym({x, y})≤cmax then there exist constants C1, C2>0and integer d∗≥0such that for sufficiently large T, C1Td∗≤Vx0(T)≤C2Td∗ In particular, dimcomp(x0) = d∗. Proof in Appendix A.3, using linear relationship between edge counts and step counts to reduce complexity balls to step balls, and utilizing volume growth estimates for bounded-degree graphs. Proposition 3.3 (Exponential Growth and Super-Polynomial Complexity).If there exist constants λ > 1and T0>0such that for all n∈N, Vx0(nT0)≥λn then dimcomp(x0) = ∞. In other words, exponential growth of complexity ball volume implies infinite complexity dimension. 5 Proof in Appendix A.4. These results show: when complexity dimension is finite, growth of complexity with budget Thas some “dimension controllability”; while exponential growth means local “explosion” in complexity geometry, corresponding to highly intractable search spaces. 4 Discrete Ricci Curvature and Problem Difficulty In metric spaces, the sign of Ricci curvature is closely related to volume growth and geodesic deviation. This section introduces a discrete Ricci curvature on complexity graphs, characterizing divergence or contraction of complex paths in local regions, and discusses qualitative connections with complexity volume growth. 4.1 Discrete Ricci Curvature Based on Transition Distributions We adopt coarse Ricci curvature based on first-order Wasserstein distance, adapted for directed weighted graphs. Definition 4.1 (Local One-Step Transition Distribution).On complexity graph Gcomp = (X, E, w), define the local one-step transition distribution from xas mx(y) = a(x, y) Pza(x, z) where a(x, y) = (exp(−λw(x, y)),(x, y)∈E, 0,otherwise, and λ > 0 is a fixed scale parameter. This is a random walk kernel biased toward “low-cost edges.” Definition 4.2 (Ricci Curvature on Complexity Graph).For x=y, define the discrete Ricci curvature from xto yas κ(x, y)=1−W1(mx, my) d(x, y) where W1is the first-order Wasserstein distance relative to complexity distance d. When the average displacement of mass between mxand myunder dis less than d(x, y), we have κ(x, y)>0; conversely if average displacement exceeds d(x, y), then κ(x, y)<0. 4.2 Curvature and Geodesic Divergence In classical metric spaces, Ricci curvature lower bounds control “average contraction” between geodesics. In our complexity graphs, we can prove a discrete analog. Theorem 4.3 (Curvature Lower Bound and Complexity Distance Contraction).Suppose there exists constant K∈Rsuch that for all adjacent vertices x, y (i.e., d(x, y)bounded), κ(x, y)≥K. Then for any two initial distributions µ, ν, their distributions µP, νP after one random walk (where Pis the transition operator) satisfy W1(µP, νP)≤(1 −K)W1(µ, ν) 6 In particular, when K > 0, Wasserstein distance decays exponentially; when K < 0, distance expands exponentially. Proof in Appendix B.1. The proof uses the definition of κ(x, y) and discrete Kantorovich duality to estimate behavior of Dirac distributions, extending to general distributions. 4.3 Curvature and Complexity Volume Growth There exist qualitative connections between curvature lower bounds and volume growth. Theorem 4.4 (Polynomial Growth Under Non-Negative Curvature).Assume the complexity graph is a locally finite directed graph with bounded symmetric version degree, and there exists K≥0such that for all adjacent x, y,κ(x, y)≥K. Then there exist constants C, d∗and T0>0such that for all T≥T0, Vx0(T)≤CTd∗ In particular, dimcomp(x0)≤d∗. Theorem 4.5 (Exponential Growth Under Strictly Negative Curvature).Assume there exist K0>0and δ > 0such that for all point pairs satisfying d(x, y)≤δ,κ(x, y)≤ −K0. Then there exist constants c, λ > 1and T0>0such that for all n∈N, Vx0(nT0)≥cλn These two theorems show that non-negative curvature controls complexity volume growth polynomially, while local strictly negative curvature leads to exponential explosion of complexity space. Proof ideas borrow from Bishop–Gromov comparison theory and Gromov hyperbolic space volume growth estimates in continuous cases, but performed entirely on discrete graphs; see Appendices B.2 and B.3. 5 Reachable Domains, Complexity Horizons, and Phase Transitions This section discusses topological evolution of reachable domain families {BT(x0)}as complexity budget Tincreases, characterizing complexity phase transitions using simple algebraic topological indicators. 5.1 Definition of Complexity Horizon Definition 5.1 (Complexity Horizon).For fixed starting point x0, call a sequence {T(k) c}k∈K⊂ (0,∞) a complexity horizon point family if for each T(k) cthere exists a topological invariant I(e.g., number of connected components, first Betti number, fundamental group order) such that when Tcrosses a neighborhood of T(k) c,I(BT(x0)) undergoes a jump. In practice, the simplest choices are number of connected components and first Betti number. 7 Definition 5.2 (Connectivity Phase Transition).Let cc(T) denote the number of connected components of BT(x0) in the symmetric graph. If there exists Tcsuch that lim ε↓0cc(Tc−ε)>lim ε↓0cc(Tc+ε) then Tcis called a connectivity complexity phase transition point. Definition 5.3 (Cycle Structure Phase Transition).Let b1(T) denote the first Betti number (number of cycles) of BT(x0). If there exists Tcsuch that b1(Tc−ε)=b1(Tc+ε) for any sufficiently small ε > 0, then Tcis called a cycle structure complexity phase transition point. 5.2 Phase Transitions and Curvature Comparison In strongly negative curvature regions, complexity balls often rapidly include large numbers of “new paths,” leading to rapid cycle number growth; while in non-negative curvature regions, complexity ball expansion is relatively mild, with cycle structure growth suppressed. We have the following qualitative propositions. Proposition 5.4 (Cycle Growth Constraint Under Local Non-Negative Curvature).Assume there exists R > 0such that within BR(x0), all adjacent point pairs have curvature satisfying κ(x, y)≥0, and the graph has bounded degree. Then there exist constants C1, C2>0such that for T≤R, b1(T)≤C1Vx0(T) + C2 In particular, if Vx0(T)is polynomially bounded, then b1(T)also grows at most polynomially. Proof in Appendix C.1. Proposition 5.5 (Rapid Cycle Appearance Under Local Negative Curvature).If in some annular layer A=BT2(x0)\BT1(x0), there exist many point pairs x, y satisfying κ(x, y)≤ −K0with bounded d(x, y), then as Tincreases from T1to T2, there exists at least one cycle structure phase transition point Tc∈(T1, T2). Proof in Appendix C.2. These results show that curvature not only controls volume growth but also determines appearance of complexity horizons and “structural phase transitions” to some extent. This provides geometric interpretation for algorithms experiencing “sudden insights” or “structural leaps” when increasing resources. 6 Manifold Limits and Unified Time Scale This section discusses how complexity graphs converge to a Riemannian manifold when computational universes have good continuous limits, how discrete complexity distances approximate continuous geodesic distances, and discusses consistency between unified time scale κ(ω) and complexity metrics. 8 6.1 Manifold Limits of Complexity Graphs Consider a family of computational universes {U(h) comp}h>0, where hdenotes discrete scale (e.g., lattice spacing, control parameter step), corresponding to complexity graphs G(h) comp = (X(h), E(h), w(h)) and distances d(h). Definition 6.1 (Gromov–Hausdorff Convergence).If there exist Riemannian manifold (M, G) with point θ0∈ M, and embedding maps Φh:X(h)→ M, such that for any bounded R > 0: 1. Φh(B(h) R(x(h) 0)) Hausdorff converges to BR(θ0) in M; 2. For all x, y ∈B(h) R(x(h) 0), lim h→0dG(Φh(x),Φh(y)) = lim h→0d(h)(x, y) then the complexity graph family (X(h), d(h)) is said to converge locally in Gromov–Hausdorff sense to (M, dG). Here dGis the geodesic distance induced by Riemannian metric G. Theorem 6.2 (Rigorous Convergence in One Dimension).Suppose for each h > 0, complexity graph G(h) comp has vertices X(h)=hZ∩[−L, L], directed edges E(h)={(x, x ±h)}, edge weights w(h)(x, x ±h) = c(x)h, where c: [−L, L]→(cmin, cmax)is a continuous positive function. Then as h→0, the metric space (X(h), d(h))converges in Gromov–Hausdorff sense to the Riemannian manifold (M, G)on interval [−L, L], where M= [−L, L]and the metric is G(θ) = c(θ)2dθ2 The geodesic distance is dG(θ1, θ2) = Zθ2 θ1 c(θ) dθ and for any θ1, θ2∈[−L, L], lim h→0d(h)(θ(h) 1, θ(h) 2) = dG(θ1, θ2) where θ(h)∈X(h)are nearest point samples. Proof in Appendix D.1. This is a rigorous version of “discrete cost sum →continuous path integral” in one dimension. Higher-dimensional cases can be obtained through similar constructions. Under appropriate regularity and locality assumptions, a family of complexity graphs can converge to some manifold (M, G), where Gis determined by second-order structure of local cost function families. 9