The length-complexity conjecture for dynamical bordisms

From papers

Let (M,X)(M,X) be a dynamical bordism with reaching function ρ(M,X):NN\rho_{(M,X)}:\mathbb{N}\dashrightarrow\mathbb{N}, and let g0g_0 be the distinguished metric on a clean bordism, flat within each standard tube. For a flow φt\varphi_t of XX, with tnt_n the time at which the trajectory from nn reaches the outgoing boundary, define

LenC(M,g0)(n)=0tnXφt(n)g0dt.\operatorname{LenC}_{(M,g_0)}(n)=\int_0^{t_n}\lVert X_{\varphi_t(n)}\rVert_{g_0}\,dt.

Length-complexity conjecture. Let f:NNf:\mathbb{N}\dashrightarrow\mathbb{N} be a partial recursive function. Given a Turing machine G\mathcal{G}, for any nNn\in\mathbb{N} let T(n)T(n) be the number of steps that MM performs when started with input nn before halting. If MGM_{\mathcal{G}} is the dynamical bordism resulting from thickening the graph G\mathcal{G}, then

limnLenC(MG,g0)T(n)=1.\lim_{n\to\infty}\frac{\operatorname{LenC}_{(M_{\mathcal{G}},g_0)}}{T(n)}=1.

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

No solutions have been posted yet.