{"id":"arxiv/2601.09109","url":"https://arxiv.org/abs/2601.09109","tags":["math.DS","cs.CC"],"score":0,"title":"Correspondences in computational and dynamical complexity I","domain":"math.DS","source":"arxiv","authors":["Samuel Everett"],"reviews":0,"subject":"math.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-14","reactions":{}}