pith. sign in

arxiv: 2602.07685 · v2 · submitted 2026-02-07 · 💻 cs.CC · math.DS

Expansive homeomorphisms on complexity quasi-metric spaces

Ya\'e U. Gaba This is my paper

Pith reviewed 2026-05-16 06:00 UTC · model grok-4.3

classification 💻 cs.CC math.DS
keywords expansive homeomorphismscomplexity quasi-metricscaling transformationsasymptotic complexity classesdynamical systemstime hierarchy theoremhyperbolic coordinatestopological entropy
0
0 comments X

The pith

Scaling transformation on complexity functions is expansive exactly when the factor differs from one

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that multiplying a complexity function f by a constant α yields an expansive homeomorphism on the space equipped with Schellekens' quasi-metric precisely when α is not 1. The sets of functions that remain close under repeated scaling coincide with the usual asymptotic complexity classes such as polynomial or exponential time. The construction supplies a dynamical-systems reading of these classes and directly ties orbit separation to the Hartmanis-Stearns time hierarchy theorem. It further computes hyperbolicity rates and topological entropy for the scaling map.

Core claim

The scaling transformation ψ_α(f)(n)=α f(n) is expansive on the complexity space (C,d_C) if and only if α≠1. The δ-stable sets of this dynamics coincide with asymptotic complexity classes. The canonical coordinates of ψ_α are hyperbolic with contraction rate λ=1/α, and orbit separation connects to the classical time hierarchy theorem of Hartmanis and Stearns. Unstable sets, conjugate dynamics, and entropy estimates are also derived.

What carries the argument

The scaling map ψ_α acting on the complexity quasi-metric space (C,d_C), whose asymmetric distance encodes one-way computational comparisons

If this is right

  • When α≠1, distances between distinct orbits grow, forcing separation of functions with different growth rates.
  • The δ-stable sets under the dynamics are exactly the asymptotic complexity classes.
  • Hyperbolicity holds in canonical coordinates with explicit contraction rate 1/α.
  • Orbit separation under the map recovers the separation given by the Hartmanis-Stearns time hierarchy theorem.
  • Topological entropy and conjugate dynamics are determined by the scaling factor α.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Dynamical invariants such as entropy or stable-set structure could be used to prove new complexity separations.
  • The supplied computational code allows direct verification on concrete families such as polynomials versus exponentials.
  • The same scaling construction might characterize equivalence classes in other quasi-metric settings arising in analysis or information theory.
  • The non-expansive case α=1 leaves all complexity distinctions invariant without forcing separation.

Load-bearing premise

The results depend on the triangle inequality and asymmetry of Schellekens' specific complexity quasi-metric together with the direct transfer of expansiveness and hyperbolicity definitions from ordinary metric dynamical systems.

What would settle it

Two functions with different asymptotic growth rates whose distances under iterated scaling remain bounded when α≠1, or become unbounded when α=1, would falsify the expansiveness claim.

read the original abstract

The complexity quasi-metric of Schellekens is a topological framework in which the asymmetry of computational comparisons -- ``$A$ is at most as fast as $B$'' carrying different information than ``$B$ is at most as slow as $A$'' -- is built into the distance itself. This paper develops the theory of expansive homeomorphisms on the resulting space. The central result is that the scaling transformation $\psi_\alpha(f)(n)=\alpha f(n)$ is expansive on the complexity space $(\C,d_\C)$ if and only if $\alpha\neq 1$. The $\delta$-stable sets of this dynamics turn out to coincide with asymptotic complexity classes, giving a dynamical characterisation of objects familiar from complexity theory. We then show that the canonical coordinates of $\psi_\alpha$ are hyperbolic with contraction rate $\lambda=1/\alpha$, and we connect orbit separation in the dynamical system to the classical time hierarchy theorem of Hartmanis and Stearns. Unstable sets, conjugate dynamics, and topological entropy estimates for the scaling map are also worked out. Concrete algorithms and Python implementations accompany every proof, so each result can be checked computationally; SageMath snippets sit alongside the examples, and the full code is in the \href{https://github.com/gabayae/expansive-homeomorphisms-complexity-qmetric}{companion repository}.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript develops the theory of expansive homeomorphisms on Schellekens' complexity quasi-metric space (C, d_C). Its central result is that the scaling map ψ_α(f)(n) = α f(n) is an expansive homeomorphism on (C, d_C) if and only if α ≠ 1; the δ-stable sets of this dynamics coincide with asymptotic complexity classes. The paper further shows that the canonical coordinates of ψ_α are hyperbolic with contraction rate λ = 1/α, connects orbit separation to the Hartmanis-Stearns time hierarchy theorem, and derives results on unstable sets, conjugate dynamics, and topological entropy estimates. Every proof is accompanied by concrete algorithms and Python implementations (with a companion repository), enabling computational verification.

Significance. If the results hold, the work supplies a dynamical-systems characterization of asymptotic complexity classes via stable sets of an expansive map, together with a direct link between orbit separation and the classical time hierarchy theorem. The explicit provision of machine-checkable code and algorithms for every claim is a clear strength, enhancing verifiability and reproducibility in theoretical computer science.

minor comments (2)
  1. [§2.2] §2.2, Definition 2.4: the transfer of the classical expansiveness definition to the quasi-metric is stated without an explicit verification that the asymmetry of d_C preserves the separation property under iteration; a short lemma confirming that the quasi-triangle inequality does not interfere with the divergence argument would strengthen the claim.
  2. [Introduction] The repository link is given, but the text does not specify which proofs are accompanied by code versus which rely on manual verification; an explicit mapping (e.g., “Algorithm 3.1 implements the proof of Theorem 3.2”) would improve traceability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The summary correctly identifies the central result on the scaling map ψ_α being expansive precisely when α ≠ 1, along with the identification of δ-stable sets with asymptotic complexity classes and the connections to the Hartmanis-Stearns theorem. We appreciate the emphasis placed on the machine-checkable algorithms and repository. No major comments appear in the report, so we have no specific points requiring rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from axioms

full rationale

The central claims are direct equivalences derived from the explicit form of Schellekens' quasi-metric d_C(f,g) = sup_n 2^{-n} max(0, f(n)-g(n)) together with the verbatim transfer of the classical expansiveness definition. The scaling property d_C(ψ_α(f), ψ_α(g)) = α d_C(f,g) immediately implies divergence of distances along orbits precisely when α ≠ 1, and the δ-stable sets coincide with asymptotic classes because d_C(f,g)=0 exactly when f ≤ g pointwise. These reductions use only the given definitions and the triangle/asymmetry properties of the quasi-metric; no fitted parameters, self-citation chains, or smuggled ansatzes appear as load-bearing steps. The paper is therefore internally consistent against its own stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the pre-existing definition of Schellekens' complexity quasi-metric and on standard notions of expansiveness and hyperbolicity from dynamical systems. No new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Schellekens' complexity quasi-metric d_C satisfies the required asymmetry and triangle inequality properties used to prove expansiveness and hyperbolicity.
    Invoked when transferring classical dynamical-systems definitions to the space (C, d_C).

pith-pipeline@v0.9.0 · 5538 in / 1461 out tokens · 31221 ms · 2026-05-16T06:00:20.908838+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Abramsky, A

    S. Abramsky, A. Jung, Domain theory, in: S. Abramsky, D.M. Gabbay, T.S.E. Maibaum (Eds.), Handbook of Logic in Computer Science , vol. 3, Oxford University Press, 1994, pp. 1–168

    work page 1994

  2. [2]

    Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms , Lecture Notes in Mathematics, vol

    R. Bowen, Equilibrium States and the Ergodic Theory of Anosov Diffeomorphisms , Lecture Notes in Mathematics, vol. 470, Springer-Verlag, 1975

    work page 1975

  3. [3]

    Cobzaş, Functional Analysis in Asymmetric Normed Spaces , Frontiers in Mathematics, Birkhäuser/Springer, 2013

    Ş. Cobzaş, Functional Analysis in Asymmetric Normed Spaces , Frontiers in Mathematics, Birkhäuser/Springer, 2013

    work page 2013

  4. [4]

    Hartmanis, R

    J. Hartmanis, R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285–306

    work page 1965

  5. [5]

    H.-P. A. Künzi, Nonsymmetric topology, Bolyai Soc. Math. Stud. 4 (1995), 303–338

    work page 1995

  6. [6]

    H.-P. A. Künzi, Nonsymmetric distances and their associated topologies: about the origins of basic ideas in the area of asymmetric topology, in: C.E. Aull, R. Lowen (Eds.), Handbook of the History of General Topology , vol. 3, Kluwer Academic Publishers, 2001, pp. 853–968

    work page 2001

  7. [7]

    Olela Otafudu, D

    O. Olela Otafudu, D. P. Matladi, M. S. Zweni, Expansive homeomorphisms on quasi-metric spaces, Appl. Gen. Topol. 25 (2024), 1–15. Expansive homeomorphisms on complexity quasi-metric spaces 26

    work page 2024

  8. [8]

    W. L. Reddy, Expansive canonical coordinates are hyperbolic, Topology Appl. 15 (1983), 205– 210

    work page 1983

  9. [9]

    Romaguera, M

    S. Romaguera, M. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999), 311–322

    work page 1999

  10. [10]

    Schellekens, The Smyth completion: a common foundation for denotational semantics and complexity analysis, Electron

    M. Schellekens, The Smyth completion: a common foundation for denotational semantics and complexity analysis, Electron. Notes Theor. Comput. Sci. 1 (1995), 535–556

    work page 1995

  11. [11]

    D. S. Scott, Domains for denotational semantics, in: M. Nielsen, E.M. Schmidt (Eds.), Au- tomata, Languages and Programming , Lecture Notes in Computer Science, vol. 140, Springer- Verlag, 1982, pp. 577–610

    work page 1982

  12. [12]

    W. R. Utz, Unstable homeomorphisms, Proc. Amer. Math. Soc. 1 (1950), 769–774

    work page 1950