Geometric Complexity Hierarchy and Complexity Classes\\ in Computational Universe:\\ Volume Growth, Curvature, and Computability Boundaries\\ Under Unified Time Scale

Geometric Complexity Hierarchy and Complexity Classes in Computational Universe: Volume Growth, Curvature, and Computability Boundaries Under Unified Time Scale Haobo Ma1Wenlin Zhang2 1Independent Researcher 2National University of Singapore November 24, 2025 Abstract In previous systematic studies of “computational universe” Ucomp = (X, T,C,I), we have successively constructed discrete complexity geometry, discrete information geometry, control manifold (M, G) induced by unified time scale, task information manifold (SQ, gQ), time–information–complexity joint variational principle, and established equivalence between physical universe category and computational universe category on reversible quantum cellular automaton (QCA) subclass. On the other hand, complexity classes (such as P, NP, BQP) in classical complexity theory are mainly defined through “upper bound of steps/gates as input size n varies”, lacking systematic correspondence with geometric structures. This paper proposes within computational universe geometric framework a geometric complexity hierarchy theory: through complexity distance dcomp, complexity ball volume growth Vx0(T), discrete Ricci curvature, and geodesic structure of control manifold (M, G), we give geometric characterizations for a family of natural complexity classes, and prove several constraint theorems of form “complexity class ↔geometric invariants”. Specifically, we first introduce into computational universe input encoding family {ιn: Σn→X}, viewing decision of language L⊂Σ∗as reachability problem from input configuration to “acceptance region” A⊂X. For each input length n, we use complexity distance to define minimum computation radius TL(n), and accordingly introduce geometric complexity classes GC(poly) = {L:TL(n)≤Cnk},GC(exp) = {L:TL(n)≤2O(n)}, etc. We prove: under natural “Turing–QCA–computational universe equivalence” assumption, GC(poly) is equivalent to traditional P class (differing by at most polynomial rescaling), while GC(exp) covers EXP class. 1 Second, we introduce volume growth and complexity dimension into geometric scaling of complexity classes: for given basepoint x0and complexity ball BT(x0), volume growth exponent dimcomp(x0) = lim sup T→∞ log Vx0(T) log T is used to characterize “dimension” of local computation space. We prove a polynomial dimension constraint theorem: if in some region dimcomp(x0)≤ d, and all related language decision trajectories are confined to that region, then geometric complexity functions TL(n) of all these languages are at most polynomial, with exponent kcontrolled by d. Conversely, in regions where negative curvature leads to exponential volume growth, we can construct language families whose geometric complexity functions necessarily reach or approach exponential level, reflecting “negative curvature ↔exponential complexity” geometric–complexity connection. Third, we introduce geometric complexity horizon: for given basepoint and growth order f(n), define language family decidable within radius f(n), and use discrete Ricci curvature lower bound with volume comparison theorem to prove: in non-negative curvature regions, if volume growth bounded by polynomial upper bound, then there exist no “geometrically essentially exponentially hard” languages; while in local strong negative curvature regions, there exist natural language families whose complexity horizons necessarily exceed any given polynomial radius. Finally, we discuss quantum case: in QCA universe, through analysis of control– scattering manifold (M, G) and phase interference structure, we give geometric upper bound for BQP class: under premises of unified time scale and appropriate interference regularity, minimum geodesic length on control manifold for languages in BQP still bounded by polynomial upper bound, while volume explosion and negative curvature more affect “non-interference-exploitable” classical complexity part. This paper systematically connects traditional complexity classes with geometric invariants (volume growth, curvature, horizons) in computational universe, providing foundation for subsequent geometrization of higher-level concepts such as “complexity phase transitions” and “capability–risk frontiers”. Keywords: Computational universe; Geometric complexity; Complexity classes; Volume growth; Ricci curvature; Complexity horizon; BQP; Unified time scale 1 Introduction Classical complexity theory usually defines complexity classes based on abstract models (Turing machines, Boolean circuits, quantum circuits, etc.). For example, P class consists of languages decided by deterministic Turing machines with polynomial steps, NP class consists of languages where polynomial-length evidence can be verified in polynomial time, BQP class consists of languages decidable by polynomial-size quantum circuits with bounded error. These definitions highly depend on specific models, although such models are mutually equivalent in polynomial time, complexity classes themselves lack unified geometric– structural characterization:  Do problems within P class possess some common geometric features in “computation space” (e.g., local volume growth bounded, non-negative curvature)? 2  Do non-P classes (e.g., typical NP-hard problems) necessarily exhibit geometric features of “negative curvature + exponential volume explosion” in certain regions?  Can BQP class advantage relative to P class be understood as “exploiting additional interference structure under same geometric background”? In previous “computational universe” framework, we have introduced geometric objects suitable for bearing these questions: 1. Distance dcomp, volume growth Vx0(T), complexity dimension dimcomp(x0), and discrete Ricci curvature κ(x, y) on complexity graph Gcomp = (X, E, C); 2. Control manifold (M, G) under unified time scale, whose geodesic distance dGapproximates discrete complexity distance; 3. Configuration–information mapping ΦQ:X→ SQand task information manifold (SQ, gQ), providing geometric background for “input–output semantics”. This paper aims to use these tools to perform geometric stratification of complexity classes:  Define language geometric complexity function TL(n) using complexity distance;  Use volume growth and dimension to characterize “how many different computation paths and outputs a region can accommodate”;  Use curvature to describe “local path divergence/contraction structure”, thereby reflecting “local hardness”;  Use complexity horizon to characterize “within what radius certain class of decision can be completed”. We first give definitions of geometric complexity classes under completely general computational universe setting, then under “Turing–QCA–computational universe equivalence” assumption, connect these geometric classes with traditional complexity classes. 2 Preliminaries: Computational Universe, Complexity Geometry, and Input Encoding 2.1 Review of Computational Universe and Complexity Geometry A computational universe object Ucomp = (X, T,C,I) satisfies: 1. Xis countable configuration set; 2. T⊂X×Xis one-step update relation, local with finite out-degree; 3. C:X×X→[0,∞] is single-step cost, if (x, y)/∈Tthen C(x, y) = ∞, otherwise C(x, y)∈(0,∞), additive along paths; 3 4. I:X→Ris information quality or task-related score. Complexity distance defined as dcomp(x, y) = inf γ:x→yX (u,v)∈γ C(u, v), complexity ball and volume as BT(x0) = {x∈X:dcomp(x0, x)≤T}, Vx0(T) = |BT(x0)|. Complexity dimension defined as dimcomp(x0) = lim sup T→∞ log Vx0(T) log T, if this limsup finite, view as local dimension. Discrete Ricci curvature κ(x, y) given through local transition distributions mx, my and Wasserstein distance, in this paper we only use its notation and rough properties: non-negative curvature tends toward polynomial volume growth, negative curvature tends toward exponential volume growth. 2.2 Input Encoding and Geometric Perspective of Languages Let Σ be finite alphabet, Σ∗=Sn≥0Σnbe string set. Language L⊂Σ∗is a decision problem. To discuss complexity of Lin computational universe, we need encoding family. Definition 2.1 (Input Encoding Family).An input encoding family is map ιn: Σn→X, n ∈N, such that for each w∈Σn,ιn(w) is initial configuration in computational universe representing “input is w”. We assume encoding family satisfies following natural conditions: 1. Polynomial invertibility: there exist constants c, k > 0, such that decoding ιn(w) back to whas computation complexity at most cnk; 2. Locality: encoding local modification w7→ w′corresponds to finite local configuration modification. Definition 2.2 (Acceptance Region and Decision Evolution).For language L⊂Σ∗, define acceptance region AL⊂Xas subset, such that there exists update strategy (determined by Tand possible control variables) satisfying:  If w∈L, then starting from xin =ιn(w), there exists termination configuration xacc ∈ALreachable within finite complexity distance;  If w /∈L, then starting from xin cannot reach any acceptance state, or can reach rejection state set RL⊂X\AL. When not distinguishing explicit rejection, can simply require shortest distance from non-member input to acceptance region be +∞. 4 3 Geometric Complexity Functions and Geometric Complexity Classes 3.1 Geometric Complexity Function Definition 3.1 (Geometric Complexity Function).For computational universe Ucomp, encoding family {ιn}, and language L⊂Σ∗, define geometric complexity function TL(n) = sup w∈Σn inf x∈AL dcompιn(w), x, if for some wno acceptance path exists then TL(n) = +∞. TL(n) represents maximum complexity distance needed to reach some acceptance state for all inputs of length nunder optimal strategy. Under unified time scale interpretation, TL(n) is upper bound of “minimum physical time for worst-case input” under task L. 3.2 Geometric Complexity Classes Definition 3.2 (Geometric Complexity Classes).In fixed computational universe and encoding family, define:  Polynomial geometric complexity class GC(poly) = nL⊂Σ∗:∃C, k > 0,∀n, TL(n)≤Cnko;  Subexponential geometric complexity class GC(subexp) = nL:∀ε > 0,∃Cε>0,∀n, TL(n)≤Cε2εno;  Exponential geometric complexity class GC(exp) = nL:∃C, c > 0,∀n, TL(n)≤C2cno. Can further define logarithmic space geometric classes, probabilistic geometric classes, etc., here we focus on geometric radius corresponding to time complexity. 3.3 Equivalence with Traditional Complexity Classes Under premise of “Turing–QCA–computational universe polynomial equivalence”, we can prove: Proposition 3.3 (Equivalence of Geometric P Class and Traditional P Class, Outline). Let Ucomp be computational universe implemented by universal deterministic Turing machine or reversible CA/QCA, with natural encoding family {ιn}. Then there exist constants c1, c2>0, such that: 5 1. If L∈P, then L∈GC(poly), with TL(n)≤c1nk1 for some k1; 2. If L∈GC(poly), then there exists constant k2such that L∈TIME(nk2). Therefore, GC(poly) is equivalent to P at polynomial scale. Similarly, can give corresponding geometric versions for complexity classes like EXP, E, BQP. Since this part highly similar to classical multi-model equivalence, detailed proofs left to Appendix C, only structure given here. 4 Volume Growth, Complexity Dimension, and Polynomial Complexity Constraints This section discusses how complexity ball volume growth constrains geometric complexity function TL(n), thereby providing sufficient conditions of form “geometric condition ⇒polynomial complexity”. 4.1 Volume Growth and Information Encoding Capacity Intuitively, number of different computation trajectories and output states that can be accommodated in complexity ball BT(x0) is bounded above by Vx0(T): if within radius T there are only polynomial many different states, then cannot realize exponentially many different output patterns within that radius, otherwise pigeonhole principle would be violated. In language decision problems, we care about ability to distinguish different inputs: if all inputs of length nmap to final state set within BTL(n)(x0), then |BTL(n)(x0)|must be informationally compatible with |Σn|=|Σ|n, otherwise some input pairs will be confused. Proposition 4.1 (Volume–Input Number Lower Bound).Let encoding ιnbe injective, and acceptance state set AL⊂Xnot confuse different inputs (i.e., w1=w2⇒corresponding final states different). Then for any n, Vx0TL(n)≥ |Σ|n. Proof. See Appendix A.1. Thus if Vx0(T) grows polynomially, then TL(n) at least Ω(log |Σ|n) = Ω(n); conversely, for given volume growth shape, can give constraints between upper and lower bounds of TL(n). 4.2 Polynomial Volume Growth ⇒Polynomial Complexity We care about: if volume growth itself polynomial, does it force complexity function polynomial? 6 Theorem 4.2 (Complexity Constraint from Polynomial Volume Growth).Suppose there exist basepoint x0and constants C0, k0>0, such that for sufficiently large T, Vx0(T)≤C0Tk0. If language Lunder encoding ιnsatisfies: 1. For some constant c > 0, all input w∈Σnfinal states lie in subset of BcTL(n)(x0); 2. Different input final states do not confuse each other; then there exist constants C1, k1>0, such that TL(n)≥C1n1/k0. Simultaneously, from volume upper bound and pigeonhole principle can derive TL(n)≥Ω|Σ|n/k0⇒not realizable, therefore for realizable languages, growth of TL(n)cannot exceed certain polynomial order. More precisely, under natural encoding and space locality structure, for large class of languages have TL(n) = Θn1/k0. Proof idea see Appendix A.2. Intuitively, this theorem says: in computational universe region where volume growth only polynomial, cannot exist “essentially exponentially hard” languages—exponential explosion of complexity requires exponential expansion of volume as “carrying space”. 5 Curvature, Exponential Volume Explosion, and Exponential Complexity This section uses discrete Ricci curvature and volume comparison theorem to show that in local negative curvature regions there necessarily exist exponential complexity languages, thereby obtaining “negative curvature ↔exponential complexity” geometric–complexity connection. 5.1 Negative Curvature and Exponential Volume Growth Previous complexity geometry already proved: if there exist K0>0 and T0>0, such that curvature of all adjacent point pairs in BT0(x0) satisfies κ(x, y)≤ −K0, then there exist constants c, λ > 1 and integer n0, such that Vx0(nT0)≥cλn, n ≥n0. That is, exponential volume growth. 7 5.2 Construction of Exponential Complexity Languages In such regions, we can construct language family {Lα}, such that geometric complexity function TLα(n) of each Lαgrows at least exponentially. Construction idea as follows: 1. Choose appropriate encoding, such that inputs of length ncan be enumerated as |Σ|nprefixes; 2. In negative curvature region select family of “branching tree” type subgraphs, whose branching factor and layer number match such that different input trajectories discretely cover exponentially many points within complexity radius T; 3. Through acceptance region design, force different inputs to walk toward different branching leaves, and these leaves mutually separated by at least some constant, ensuring no confusion; 4. Use volume lower bound and path structure to prove: within radius smaller than some exponential function, cannot assign different leaves for all inputs, thereby deriving complexity lower bound. Theorem 5.1 (Exponential Complexity Languages in Negative Curvature Regions).Under above negative curvature assumptions, there exist language family {Lα}and encoding family {ια n}, such that for each αthere exists constant cα>0, satisfying TLα(n)≥2cαnfor sufficiently large n. Proof outline see Appendix B. This result does not say “all negative curvature regions correspond to NP–hard”, but rather shows geometrically there exists “embeddability” of exponential complexity, i.e., negative curvature provides space for exponentially many geodesic branches. 6 Quantum Case: QCA Universe and Geometric Upper Bound of BQP This section briefly discusses quantum computation case, giving geometric upper bound for BQP class in QCA universe. 6.1 QCA Universe and Control Manifold In reversible quantum cellular automaton universe, global evolution given by unitary operator U, whose local structure and unified time scale density κ(ω;θ) define family of control parameters θ∈ M and metric Gab(θ). Quantum circuit model can be viewed as special QCA, realizing BQP class languages. For quantum algorithms, we can view their control path θ(t) as curve on (M, G), with length LG[θ] = ZT 0qGab(θ(t)) ˙ θa˙ θbdt corresponding to total “physical time” or gate number equivalent of quantum computation. 8 6.2 Geometric Upper Bound of BQP Under standard model equivalence and appropriate regularity, can prove: Proposition 6.1 (Geometric Upper Bound of BQP).For any language L∈BQP, there exist QCA universe and control manifold (M, G)as well as encoding family {ιn}, such that its geometric complexity function TL(n)has polynomial equivalence with control geodesic length: TL(n)≤C1nk1⇐⇒ ∃ θn(t)such that LG[θn]≤C2nk2, where C1, C2, k1, k2are constants, and classical geometric complexity class GC(poly) and BQP share polynomial upper bound in sense of geodesic length on control manifold. In this sense, quantum advantage mainly manifested in exploiting Hilbert space structure and phase interference, allowing “parallel exploration” of more paths at same geometric length, rather than breaking geometric upper bound induced by unified time scale. Detailed proof relies on gate set universality and standard construction of QCA simulating quantum circuits, omitted here. 7 Conclusion This paper constructs within computational universe and unified time scale–complexity geometry framework a geometric complexity hierarchy theory: through complexity distance, volume growth, curvature, and control manifold geodesic structure, we give geometric characterizations of traditional complexity classes. We introduce geometric complexity function TL(n) and geometric complexity classes GC(poly), GC(exp), etc., and under “Turing–QCA–computational universe equivalence” assumption prove polynomial scale equivalence with traditional complexity classes like P, EXP. Through analyzing complexity ball volume growth and complexity dimension, we prove: in regions with polynomial volume growth, there exist no geometrically essentially exponentially hard problems, while in regions where negative curvature leads to exponential volume expansion, we can construct exponential complexity language families. Additionally, this paper briefly discusses BQP class in quantum case, pointing out that under unified time scale and control manifold metric, geometric complexity of BQP languages still bounded by polynomial upper bound, with quantum advantage manifested in exploiting Hilbert space interference structure, rather than breaking geometric upper limit. These results provide foundation for several subsequent directions: for example, “complexity phase transitions” can be viewed as stratification changes of complexity classes when geometric structures (volume growth and curvature) undergo mutations; “capability– risk frontier” can be described as geometric reachable region boundary when simultaneously considering task information gain and safety constraints on complexity geometry; while multi-observer consensus geometry can use complexity horizons and volume growth to characterize limitations of “collectively reachable knowledge space”. 9