Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.09109 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915728016277504 |
|---|---|
| author | Everett, Samuel |
| author_facet | Everett, Samuel |
| contents | We begin development of a method for studying dynamical systems using concepts from computational complexity theory. We associate families of decision problems, called telic problems, to dynamical systems of a certain class. These decision problems formalize finite-time reachability questions for the dynamics with respect to natural coarse-grainings of state space. Our main result shows that complexity-theoretic lower bounds have dynamical consequences: if a system admits a telic problem for which every decider runs in time $2^{Ω(n)}$, then it must have positive topological entropy. This result and others lead to methods for classifying dynamical systems through proving bounds on the runtime of algorithms solving their associated telic problems, or by constructing polynomial-time reductions between telic problems coming from distinct dynamical systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09109 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Correspondences in computational and dynamical complexity I Everett, Samuel Dynamical Systems Computational Complexity 37B40, 03D15, 37M99 We begin development of a method for studying dynamical systems using concepts from computational complexity theory. We associate families of decision problems, called telic problems, to dynamical systems of a certain class. These decision problems formalize finite-time reachability questions for the dynamics with respect to natural coarse-grainings of state space. Our main result shows that complexity-theoretic lower bounds have dynamical consequences: if a system admits a telic problem for which every decider runs in time $2^{Ω(n)}$, then it must have positive topological entropy. This result and others lead to methods for classifying dynamical systems through proving bounds on the runtime of algorithms solving their associated telic problems, or by constructing polynomial-time reductions between telic problems coming from distinct dynamical systems. |
| title | Correspondences in computational and dynamical complexity I |
| topic | Dynamical Systems Computational Complexity 37B40, 03D15, 37M99 |
| url | https://arxiv.org/abs/2601.09109 |