Pá de cal no Empirismo?
Determining dynamical equations is hard
(Submitted on 30 Apr 2010)
Abstract: The behaviour of any physical system is governed by its underlying dynamical equations--the differential equations describing how the system evolves with time--and much of physics is ultimately concerned with discovering these dynamical equations and understanding their consequences. At the end of the day, any such dynamical law is identified by making measurements at different times, and computing the dynamical equation consistent with the acquired data. In this work, we show that, remarkably, this process is a provably computationally intractable problem (technically, it is NP-hard). That is, even for a moderately complex system, no matter how accurately we have specified the data, discovering its dynamical equations can take an infeasibly long time (unless P=NP). As such, we find a complexity-theoretic solution to both the quantum and the classical embedding problems; the classical version is a long-standing open problem, dating from 1937, which we finally lay to rest.
Comments: For mathematical details, see arXiv:0908.2128[math-ph].
Comentários