Expansive homeomorphisms on complexity quasi-metric spaces
For researchers in theoretical computer science and dynamical systems, this paper offers a novel topological-dynamical perspective on complexity classes, but the results are largely theoretical and incremental, building on existing frameworks.
This paper develops the theory of expansive homeomorphisms on Schellekens' complexity quasi-metric space, proving that the scaling transformation ψ_α is expansive iff α≠1, and showing that its δ-stable sets coincide with asymptotic complexity classes, thereby providing a dynamical characterization of complexity classes. The work also connects orbit separation to the classical time hierarchy theorem.
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 $ψ_α(f)(n)=αf(n)$ is expansive on the complexity space $(\C,d_\C)$ if and only if $α\neq 1$. The $δ$-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 $ψ_α$ are hyperbolic with contraction rate $λ=1/α$, 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}.