Correspondences in computational and dynamical complexity II: forcing complex reductions
By: Samuel Everett
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.
Similar Papers
The Solver's Paradox in Formal Problem Spaces
Computational Complexity
Proves math problems are harder than computers can solve.
A Study of NP-Completeness and Undecidable Word Problems in Semigroups
Computational Complexity
Proves some math problems can never be solved by computers.
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
Computational Complexity
Solves hard math problems by finding common roots.