You're reading: News, Phil. Trans. Aperiodic.

Deriving dynamical equations is NP-Hard

This paper has just been accepted by Physical Review Letters:

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this work, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP-hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

This paper has been accepted, so I can’t see why I shouldn’t be able to read it yet. Possibly something to do with money. The preprint is on the ArXiv, anyway.

via ScienceNOW via Slashdot, who reported it as “It’s Official: Physics is Hard”. That’s exactly the kind of unhelpful attention-grabbing headline we’re hoping to avoid here at The Aperiodical. ((They weren’t wrong, though: physics is hard.))

A commenter on Slashdot raises an interesting point:

Could we then map NP-HARD computation problems onto real world physics systems to find solutions?

(will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>