Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.09973 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914256165797888 |
|---|---|
| author | Everett, Samuel |
| author_facet | Everett, Samuel |
| contents | An algebraic telic problem is a decision problem in $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_09973 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Correspondences in computational and dynamical complexity II: forcing complex reductions Everett, Samuel Computational Complexity Dynamical Systems F.1.3 An algebraic telic problem is a decision problem in $\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. |
| title | Correspondences in computational and dynamical complexity II: forcing complex reductions |
| topic | Computational Complexity Dynamical Systems F.1.3 |
| url | https://arxiv.org/abs/2601.09973 |