The length-complexity conjecture for dynamical bordisms
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.