Scalar Impossibility in Multi-Pillar Complexity Measures: Why a Single Number Cannot Capture Algorithmic, Information-Theoretic, Dynamical, and Geometric Complexity

During 2024-2025, we attempted multiple scalar formulations linking complexity to thermal gradients and information-geometric bridges, ultimately discovering fundamental circular dependencies that motivated this formal proof.These empirical attempts included scalar complexity fields coupled to temperature gradients, Fisher information metrics over phase space, spectral density proxies, and discrete transition counting. Each formulation either introduced circular dependencies (fitting complexity to observed transitions), produced unbounded values, or conflated distinct operational pillars. While the broader research program on multi-pillar complexity theory remains ongoing, this impossibility result resolves the empirical frustration encountered in those earlier attempts. The theoretical result establishes why those empirical attempts necessarily failed.

Consider three systems: a quantum computer with 100 qubits running Shor’s algorithm, a hurricane’s velocity field captured at hourly intervals, and a social network graph of one million users. Which is “most complex”?

The quantum computer has high algorithmic complexity (requires many gates to prepare the state) but low topological complexity (qubits arranged in a regular grid). The hurricane has high dynamical complexity (chaotic, unpredictable) but moderate algorithmic complexity (governed by relatively simple differential equations). The social network has high geometric complexity (intricate community structure) but low dynamical complexity (changes slowly over time). We can assign each system a value $C_1^{\ast },C_2^{\ast },C_3^{\ast }$, but how should these numbers relate?

Imagine having a single number $C^{\ast }(X)$ that captures all aspects of complexity for any system $X$. This would enable direct comparisons: if $C^{\ast }(A)>C^{\ast }(B)$, then system $A$ is unambiguously more complex. Such a measure would simplify resource estimation, optimization, and theoretical predictions across physics, information theory, and computation. The dream is seductive and intuitive.

Impossibility results in related domains suggest caution. In social choice theory, Arrow’s theorem [3, 4] shows no preference aggregation can satisfy all fairness criteria simultaneously. This impossibility result parallels Arrow’s theorem in social choice theory in that both demonstrate fundamental incompatibilities between multiple ordering criteria. However, where Arrow’s theorem concerns aggregation of subjective preferences under fairness constraints (independence of irrelevant alternatives, unanimity, non-dictatorship), our result concerns objective structural properties under monotonicity requirements. The structural parallel: both show that multiple incompatible partial orders cannot be compressed into a single total order without contradiction.

In optimization, no-free-lunch theorems [36, 16] prove all algorithms have identical average performance across all problems. In multi-objective optimization [14], conflicting objectives cannot be simultaneously optimized by a single scalar without task-dependent weights. In quantum resource theory [8, 9], different choices of “free operations” lead to incompatible resource orderings, and no finite complete set of monotones exists [34]. Similarly, universal intelligence measures face Arrowian impossibilities [20].

These results share a common structure: multiple incommensurable aspects resist compression into a single number. Complexity, we will show, follows this pattern.

We organize widely used complexity notions into four families, each capturing distinct structural properties:

Each pillar comes with natural operations that increase complexity in that domain: adding gates increases $C_{\mathrm{alg}}$, mixing processes increase $C_{\mathrm{info}}$, chaotic advection increases $C_{\mathrm{dyn}}$, and topological enrichment increases $C_{\mathrm{geom}}$. The question is: can a universal scalar $C^{\ast }$ be monotone under all such operations simultaneously?

We prove the answer is no. We formalize natural axioms that any universal complexity scalar should satisfy (additivity, monotonicity, continuity, task-universality) and show these axioms are mutually incompatible. The impossibility arises not from measurement limitations but from fundamental structural conflict: the four pillars impose incompatible orderings on systems. You can construct cycles where each step increases complexity in its respective pillar, yet the cycle returns to the starting point, forcing any monotone scalar into logical contradiction.

The result implies that faithful complexity quantification requires vectors, not scalars: $𝐂=(C_{\mathrm{alg}},C_{\mathrm{info}},C_{\mathrm{dyn}},C_{\mathrm{geom}})\in {[0,1]}^4$. Task-specific scalarizations (weighted combinations) remain valid when one pillar dominates or when weights reflect problem-specific priorities, but task-universal scalars satisfying all monotonicity axioms cannot exist.

Section 2 establishes the mathematical framework: we define the system category, complexity measures, and morphism families formally. Section 3 states axioms for a universal scalar. Section 4 proves the main impossibility theorem. Section 5 discusses consequences and practical alternatives. Appendices provide explicit verifiable examples.

Before proving impossibility, we must define precisely what we mean by “complexity measure,” “improvement operation,” and “system.” The following framework provides the mathematical structure needed for rigorous argumentation. Readers familiar with category theory will recognize this as a functorial approach to complexity; others can treat it as systematic bookkeeping of systems and transformations.

Our axioms are not arbitrary but emerge from fundamental requirements for any meaningful complexity measure. They draw from established principles in physics, information theory, and computation:

These axioms thus represent the minimal requirements for a complexity measure to be physically meaningful, information-theoretically sound, and computationally invariant. That they lead to impossibility reveals a fundamental tension between universality and monotonicity.

A universal complexity scalar is a functional $C^{\ast }:\mathrm{𝖲𝗒𝗌}\to ℝ$ intended to summarize $𝐂$. We require:

(A1) Additivity:

For independent composites, where independence means:

• Classical: $X\oplus Y$ with ${\mu }_{X\oplus Y}={\mu }_X\times {\mu }_Y$ (product measure)

• Quantum: $X\otimes Y$ with ${\rho }_{X\otimes Y}={\rho }_X\otimes {\rho }_Y$ (tensor product)

we require $C^{\ast }(X\oplus Y)=C^{\ast }(X)+C^{\ast }(Y)$.

(A2a) Weak Monotonicity:

For every morphism $f$ in any pillar family ${𝖬}_{\bullet }$:

$$C^{\ast }(f(X))\ge C^{\ast }(X)$$

(A2b) Strict Monotonicity:

For every strict improvement $f$ (as defined in Definition 6):

$$C^{\ast }(f(X))>C^{\ast }(X)+{\delta }_{\bullet }$$

where ${\delta }_{\bullet }>0$ is the pillar-specific threshold.

Why both weak and strict monotonicity?

Axiom A2a alone permits degenerate solutions like $C^{\ast }(X)=\text{constant}$ for all $X$, which satisfies weak monotonicity trivially but provides no information. Axiom A2b (strict monotonicity under improvements) eliminates such degeneracies by requiring that genuine complexity-increasing operations produce measurable scalar increases. Together, A2a and A2b enforce that $C^{\ast }$ respects the partial order structure while remaining responsive to operational differences.

(A3) Scale-Continuity:

¹¹1Axiom A3 (continuity in $\lambda$) is not required for Theorem 1, which holds even for discrete parameter spaces (see Proposition 1 and Remark 7). We include it for mathematical completeness and to facilitate future extensions to continuous-scale families.

$C^{\ast }$ is continuous with respect to the product topology on $\mathrm{𝖲𝗒𝗌}\times {ℝ}_{+}$ where:

• $\mathrm{𝖲𝗒𝗌}$ has the weak-* topology (classical) or trace norm topology (quantum)

• Scale parameter $\lambda$ has the standard topology on ${ℝ}_{+}$

Explicitly: $\forall ϵ>0,\exists \delta >0$ such that implies .

(A4) Task-Universality:

$C^{\ast }$ is defined on all $(X,\lambda )\in \mathrm{𝖲𝗒𝗌}\times {ℝ}_{+}$ without reference to any specific task, algorithm, or measurement protocol beyond the normalization convention.

Relation to No-Free-Lunch.

Task-universality (A4) demands that $C^{\ast }$ work across all systems without task-specific weighting—analogous to seeking a universal optimization algorithm without problem-specific tuning. The no-free-lunch theorem [36] shows that all algorithms have identical average performance across all problems; similarly, we show that task-universal complexity scalars satisfying all monotonicity axioms cannot exist. The key distinction: NFL concerns algorithm performance; ours concerns structural quantification.

(A5) Relabeling Invariance:

A bijection $\sigma :X\to Y$ is a relabeling if and only if:

1. It permutes indices of subsystems (qubits, bits, vertices) while preserving all structure

2. For classical systems: $\sigma$ is a permutation of coordinate labels

3. For quantum systems: $\sigma$ corresponds to a permutation matrix in the computational basis

4. Crucially: $\sigma$ preserves ALL complexity measures: $C_{\bullet }(\sigma (X))=C_{\bullet }(X)$ for all $\bullet \in \{\text{alg},\text{info},\text{dyn},\text{geom}\}$

For any such relabeling: $C^{\ast }(\sigma (X))=C^{\ast }(X)$.

What is NOT a relabeling:

• Embeddings into higher-dimensional spaces (changes $C_{\mathrm{geom}}$)

• Basis changes that alter entanglement structure (changes $C_{\mathrm{info}}$)

• Time evolution or dynamics (changes $C_{\mathrm{dyn}}$)

• Compression or encoding (changes $C_{\mathrm{alg}}$)

This axiom ensures complexity does not depend on arbitrary labeling conventions (e.g., calling the first qubit “A” vs “1”) but does NOT allow ignoring structural modifications that affect any complexity pillar.

(A6) Normalization:

with $C^{\ast }(\mathrm{\varnothing })=0$ where $\mathrm{\varnothing }$ is the trivial system.

(A1) says that independent systems add their complexities—like energies in thermodynamics or entropies in information theory. (A2a,b) ensure that complexity-increasing operations actually increase the scalar; the distinction between weak and strict monotonicity prevents trivial constant functions. (A3) prevents pathological discontinuities: small perturbations shouldn’t cause complexity to jump. (A4) demands true universality: no task-specific tuning or weights. (A5) ensures complexity doesn’t depend on arbitrary labeling choices (e.g., permuting qubit labels). (A6) provides basic regularity and normalization.

While the cycle contradiction could be derived using only isomorphisms, we include the non-invertible noise step $n$ for pedagogical clarity. It demonstrates that the impossibility doesn’t rely solely on isomorphisms: even allowing operations that clearly should decrease a universal complexity measure (information-theoretic noise) doesn’t resolve the fundamental tension. The core issue is that improving each pillar via morphisms designed for that pillar creates incompatible constraints on any universal scalar.

Key properties: $n\in \mathrm{𝖲𝗒𝗌}$ (Markov/CPTP), $n$ is non-invertible (information loss), and by Axiom (A3’) strictly (non-degenerate noise).

Step 3 (Dynamical): Apply chaotic evolution: Arnold cat map on classical bits (Lyapunov exponent $\lambda >0$) and kicked Ising evolution on quantum state (scrambling time $t^{\ast }=O(\log k)$). This increases $h_{KS}$ and entanglement entropy growth rate without changing the state’s algorithmic description length.

Step 4 (Geometric): Embed in topological structure: place classical configuration on vertices of a triangulated 2-complex with non-trivial fundamental group ${\pi }_1(K)\ne 0$. Encode quantum state in surface code. This adds persistent homology features: ${\beta }_1(X_4)>{\beta }_1(X_3)$.

Step 5 (Projection): Define ${\pi }_{\mathrm{geom}}$ to extract the underlying bit string and qubit state, discarding topological structure. By construction, ${\pi }_{\mathrm{geom}}(X_4)$ has the same classical and quantum content as $X_0$.

The key observation is that each morphism targets a specific complexity type without necessarily increasing others, enabled by the independence of the four pillars. The explicit construction is detailed in Appendix A. ∎

Steps 1, 3, 4 are isomorphisms (reversible), so by Axiom (A2) applied to both $f$ and $f^{-1}$, we have $C^{\ast }(f(X))\le C^{\ast }(X)$ and $C^{\ast }(f^{-1}(f(X)))\le C^{\ast }(f(X))$, implying $C^{\ast }(f(X))=C^{\ast }(X)$ (equality for isomorphisms). These steps strictly raise their respective pillar observers but leave $C^{\ast }$ unchanged. Only Step 2 (noise $n$) is non-invertible, causing strict decrease by Axiom (A3’). The closing isomorphism $\varphi$ forces $C^{\ast }(X_0)=C^{\ast }(X_4)$, yet the chain implies —contradiction.

Imagine you propose a complexity function $C^{\ast }$. If it satisfies all our axioms for one pillar (say, algorithmic complexity), you might hope it works for all four. The theorem shows this is impossible: satisfying monotonicity for all four pillars simultaneously creates a logical contradiction.

The proof shows that trying to compress all complexity aspects into one number leads to an impossible statement: $C^{\ast }(X_0)>C^{\ast }(X_0)+\epsilon$ for some $\epsilon >0$. This isn’t due to measurement error or finite precision—it’s a fundamental logical impossibility arising from the conflicting structure of complexity types.

The impossibility doesn’t mean complexity is unmeasurable—it means we must use vectors, not scalars. This section explores practical implications.

The impossibility is fundamental for task-universal single scalars but leaves open multiple productive research directions.

When comparing systems, plot them in 4D complexity space (or project to 2D/3D for visualization). Pareto frontiers emerge: system A dominates B if $𝐂(A)\ge 𝐂(B)$ componentwise. Many systems will be incomparable—neither dominates the other—reflecting genuine trade-offs between complexity types. This vectorial approach is already used implicitly in multi-objective optimization; our result shows it’s mandatory for complexity.

Consider designing a neural network. High $C_{\mathrm{alg}}$ (many parameters) may improve accuracy but increases training time. High $C_{\mathrm{info}}$ (many inter-layer correlations) may improve expressiveness but complicates interpretation. High $C_{\mathrm{dyn}}$ (chaotic gradient dynamics) may escape local minima but hinders reproducibility. High $C_{\mathrm{geom}}$ (intricate loss landscape topology) may enable diverse solutions but complicates optimization. There is no single “best” architecture—the optimal choice lies on the Pareto frontier and depends on task priorities (accuracy vs. speed vs. interpretability).

The impossibility suggests that proposed “complexity equals action” conjectures [6, 32] cannot be universal. Different physical processes optimize different complexity aspects, explaining the diversity of structures in nature. Black hole complexity likely requires multiple measures to capture both bulk geometry and boundary quantum information.

Just as there is no universal compression algorithm (by no-free-lunch [36]), there is no universal complexity measure. Task-specific measures remain essential. This connects to Shannon’s insight that information is context-dependent—complexity inherits this context-dependence. Partial information decomposition [35] already shows information naturally resists scalar compression; our result extends this to general complexity.

Recent work by Rosas et al. [26] characterizes emergent macroscales as “software-like” self-contained processes via Markov lumpability—the condition under which coarse-graining preserves Markov structure. They establish that a microscopic process exhibits causally and informationally closed levels if and only if its causal states are strongly lumpable, providing a rigorous criterion for identifying emergent macroscopic descriptions [17, 25].

Our impossibility result is orthogonal yet complementary to this framework. While Rosas et al. identify where emergent levels exist through lumpability conditions, we prove that regardless of such hierarchical structure, no single task-universal scalar can simultaneously respect the ordering constraints of our four complexity pillars. Even within a single strongly lumpable macroscale—where coarse-grained dynamics maintain perfect Markovian structure—the vectorial nature of complexity $𝐂\in {[0,1]}^4$ remains irreducible. This demonstrates that hierarchical emergence does not rescue scalar universality; vectorial reporting remains necessary regardless of lumpable partitioning.