Correspondences in computational and dynamical complexity II: forcing complex reductions
Samuel Everett · 2026
Read Correspondences in computational and dynamical complexity II: forcing complex reductions by Samuel Everett (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09973.txt.
Introduction
Samuel Everett links two hard fields: how hard a task is, and how a flow acts. His tasks ask if a point can reach a set in finite time. The flow is one way and sits on a line. Each task comes from its own flow.
He shows a tight link. If tasks from two flows can map to each other in a natural way, the flows must act alike. The word alike is made sharp in the proof. The paper is part two of a pair. It gives a tool to sort flows by the tasks they spawn.
Catalog record
| CREATOR | Samuel Everett |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-09973
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Correspondences in computational and dynamical complexity II: forcing complex reductions Samuel Everett Abstract . An algebraic telic problem is a decision problem in NP ℝ \textsf{NP}_{\mathbb{R}} formalizing finite-time reachability questions for one-dimensional dynamical systems. We prove that the existence of “natural” mapping reductions between algebraic telic problems coming from distinct dynamical systems implies the two dynamical systems exhibit similar behavior (in a precise sense). As a consequence, we obtain explicit barriers for algorithms solving algebraic telic problems coming from complex dynamical systems, such as those with positive topological entropy. For example, some telic problems cannot be decided by uniform arithmetic circuit families with only + + and × \times gates. 1. Introduction This paper studies the computational complexity of finite-time reachability questions derived from dynamical systems, and asks how dynamical structure constrains the kinds of algorithms that can solve them. Informally, given a dynamical system and a target region of state space, we consider decision and search problems of the form: does there exist a suitably encoded initial state whose orbit reaches the target after a prescribed number of iterates? Our aim is to develop a technique for using concepts from dynamical systems to place a priori restrictions on algorithms deciding such reachability problems. The critical insight is that the definition of a reduction between two reachability problems coming from distinct dynamical systems is nearly identical to the definition of a conjugacy of the two dynamical systems. It is natural to derive computational problems from dynamical systems, and there is a sizable literature dedicated to connecting computability and complexity theory with dynamics. Salient examples include (i) determining the computability and complexity of state-reachability and related decision problems for a fixed system [ 16 , 9 , 8 , 24 , 17 ] , and (ii) questions about when a dynamical system can simulate a universal Turing machine [ 20 , 13 , 18 , 6 , 10 , 11 , 12 ] . (See the introduction of the first part of this work [ 14 ] for a detailed overview.) These developments have produced powerful computability and complexity-theoretic tools for analyzing dynamical systems. In contrast, it is comparatively less explored how dynamical notions can be used to inform fundamental complexity-theoretic questions. The existing work in this direction has already led to deep insights (see, e.g. [ 3 , 7 , 13 ] ), and motivates the program pursued here. 1.1. Overview of main definitions and results For the purpose of this paper, a dynamical system is a pair (X,F) consisting of a set X (the state space ) and a transformation F:X\to X . In most settings of interest, X is a compact metric space and F is continuous. To witness dynamical behavior, iterate F on points x\in X , writing F^{n}(x) for the n -fold composition of F applied to x (with n\in\mathbb{N} , or n\in\mathbb{Z} when F is invertible). In this paper we consider dynamical systems (I,F) of the unit interval I=[0,1] that are computable by Blum–Shub–Smale machines : BSS-computable systems are those for which there exists a BSS-machine that on input x\in I , returns F(x)\in I . Issues of complexity do not arise in this case because the input x\in I is always of length one. An algebraic telic problem , or simply a telic problem coming from a dynamical system (I,F) is a decision problem contained in \textsf{NP}_{\mathbb{R}} , and defined as follows. Let g:I\rightarrow I be a BSS-computable homeomorphism of the unit interval (e.g. a polynomial whose restriction to I is a bijection). Let I_{m}=\{p/2^{m}:p\in[2^{m}]\} denote the precision m dyadic rationals contained in I . Then on length n+2 input (a,b,1,\dots,1) for a,b\in I and a\leq b , decide whether there is a dyadic rational y of precision n^{2} , i.e. y\in I_{n^{2}} , such that F^{n}(g(y))\in[a,b] . We denote an algebraic telic problem coming from a dynamical system (I,F) by \mathbb{R}\textsf{--TELIC}_{(I,F)}(g) . We will also work with a generalization of algebraic telic problems called bounded algebraic telic problems , defined as follows. Let (I,F) be a BSS-computable dynamical system and g:I\rightarrow I a BSS-computable homeomorphism. Let k:\mathbb{N}\rightarrow\mathbb{N} be a function computable by a polynomial-time Turing machine over a unary alphabet, and let a:\mathbb{N}\rightarrow[0,1] denote a function computable by a polynomial-time BSS machine. Then on length n+1 input (c,1,\dots,1) for c\in I , decide whether there is a precision n^{2} dyadic rational y\in I_{n^{2}} such that F^{k(n)}(g(y))\in[c-a(n),c+a(n)] . Bounded algebraic telic problems are denoted \mathbb{R}\textsf{--BTELIC}_{(I,F)}(a,k,g) . We find the most success in studying the search versions of telic problems, in which a dyadic rational y witnessing F^{n}(g(y))\in[a,b] is returned. Search versions of standard algebraic telic problems and bounded algebraic telic problems are denoted \mathbb{R}\textsf{--STELIC}_{(I,F)}(g)\text{ and }\mathbb{R}\textsf{--SBTELIC}_{(I,F)}(a,k,g),\text{ respectively}. A central idea of this paper is that writing down the form any reduction between telic problems must take comes very close to simply writing down the definition of a conjugacy of dynamical systems. In particular, if a reduction can take a certain form, it implies the underlying dynamical systems share certain characteristics. As a consequence, if two telic problems are derived from systems which do not share those characteristics (are classified differently), reductions of that type cannot go through. Although focusing on the existence of reductions between problems is an unusual approach, it is the right frame of mind to use in our setting. Moreover, studying the structure of reductions between telic problems extends to the structure of algorithms solving the problems directly: considering reductions to telic problems coming from the trivial system (I,\Id) is tantamount to considering algorithms solving the problems directly. We now make these ideas concrete. Let \mathcal{I} label the collection of all points and closed intervals contained in I , represented as the convex subset of \mathbb{R}^{2} whose points (c,r) we correspond to intervals [c-r,c+r]\subseteq I . Suppose the system (I,F) has complicated orbit structure while (I,T) is dynamically regular, so its search telic problems are solvable in polynomial time. A natural method for solving \mathbb{R}\textsf{--STELIC}_{(I,F)}(g) is to reduce it to some \mathbb{R}\textsf{--STELIC}_{(I,T)}(\hat{g}) coming from (I,T) by constructing a family of maps \{\eta_{n}\}_{n=1}^{\infty} , with each \eta_{n}:\mathcal{I}\rightarrow\mathcal{I} satisfying the property that for all x\in I_{n^{2}} and J\in\mathcal{I} , F^{n}(g(x))\in J if and only if T^{n}(\hat{g}(x))\in\eta_{n}(J) . We call such a reduction a level 3 natural search reduction from \mathbb{R}\textsf{--STELIC}_{(I,F)}(g) to \mathbb{R}\textsf{--STELIC}_{(I,T)}(\hat{g}) . We define stricter templates (levels 1–2) by imposing additional constraints on the functions \{\eta_{n}\} composing the reduction, and a more permissive template (level 4) that can be used to reduce between any two search problems, by only requiring the one-way implication T^{n}(\hat{g}(x))\in\eta_{n}(J)\Rightarrow F^{n}(g(x))\in J . Our first theorem shows that search telic problems coming from dynamically mismatched systems cannot be reduced to one another by natural reductions. Theorem 1.1 ( Theorem 5.2 ) . There exists a dynamical system (I,F) with positive topological entropy and a regular dynamical system (I,T) with zero topological entropy, both computable by BSS-machines, as well as homeomorphisms g:I\rightarrow I and \hat{g}:I\rightarrow I computable by BSS-machines, for which \mathbb{R}\textsf{--STELIC}_{(I,T)}(\hat{g})\in\textsf{P}_{\mathbb{R}} , and \mathbb{R}\textsf{--STELIC}_{(I,F)}(g) is not reducible to \mathbb{R}\textsf{--STELIC}_{(I,T)}(\hat{g}) by level 1, 2, or 3 natural search reductions. The guiding principle is that reductions between telic problems cannot ignore dynamical distinctions. If two systems are dynamically “too far