The length-complexity conjecture for dynamical bordisms
The length-complexity conjecture for dynamical bordisms
Let be a dynamical bordism with reaching function , and let be the distinguished metric on a clean bordism, flat within each standard tube. For a flow of , with the time at which the trajectory from reaches the outgoing boundary, define
Length-complexity conjecture. Let be a partial recursive function. Given a Turing machine , for any let be the number of steps that performs when started with input before halting. If is the dynamical bordism resulting from thickening the graph , then
The preceding prose motivates this claim by saying that the distinguished metric computes the Euclidean length of the flow and conjecturing asymptotic comparability with ordinary time complexity. The statement is presented in a section of refined open problems.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ángel González-Prieto, Eva Miranda and Daniel Peralta-Salas, “Universality in computable dynamical systems: Old and new”, arXiv:2507.10725 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.