Please create an account to participate in the Slashdot moderation system

 



Forgot your password?
typodupeerror
Get HideMyAss! VPN, PC Mag's Top 10 VPNs of 2016 for 55% off for a Limited Time ×
Science

Submission + - Physics is (NP-)Hard (sciencemag.org)

An anonymous reader writes: New research at the boundary of physics and computer science shows that determining the dynamical equations of a system from observations of its behavior is NP-hard:

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 discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

Physics is (NP-)Hard

Comments Filter:

"Catch a wave and you're sitting on top of the world." - The Beach Boys

Working...