The behaviour of any physical system is governed by its dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their implications. It is perhaps surprising, therefore, that identifying the underlying dynamical equation from any amount of experimental data, however precise, is a computationally hard problem (more precisely, it is NP-hard). This is true both for classical and for quantum mechanical dynamics.

As a by-product, this result finally lays to rest — in a complexity-theoretic sense — the quantum and classical embedding problems, two long-standing open problems in mathematics. (The classical problem, in particular, dates back over 70 years.)

I will explain these results, and discuss some of the possible implications they might have for physics.