[tsimionescu]

I believe that if you could prove that you have an actual isomorphism in the full formal sense of the world, the question about its complexity wouldn't really matter.

However, for a practical claim, it is probably impossible to formally prove that an interpreter function is both bijective between a physical system and a computation (it maps absolutely every possible state of the physical system to exactly one step of a computation).

However, it's important that the following argument can be made: if the evolution of a physical system is isomorphic to a computation of a particular algorithm for solving the traveling salesman problem, and if the phsyical system needs ~1 second for each step, then the system can't go from state A to state B in less than X seconds, where X is the number of steps required by that algorithm to reach those same steps. The actual interpretation of the algorithm or its purpose is not relevant here, the mathematical limits of how the computation happens remain relevant regardless.

That is because you can't find 2 different isomorphisms between the same physical system and 2 different computation that are not isomorphic to each other, if these are actual proper isomorhpisms (bijective) and not just hand-wavy analogies.