Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?

Physics Is (NP-)Hard 212

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. From the abstract: '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.'"
This discussion has been archived. No new comments can be posted.

Physics Is (NP-)Hard

Comments Filter:
  • Re:NP (Score:4, Interesting)

    by UnknowingFool ( 672806 ) on Friday February 24, 2012 @01:18PM (#39149283)

    To paraphrase and dumb it down a bit as explained to me: this problem has no solution that will solve all cases. Every case has a unique solution that has to solved more by trial and error.

    The most common example it the traveling salesman problem. If a salesman has to drive to 5 cities, what is the best way to arrange the trip to use the least amount of fuel. Since the problem is NP hard, any solution found for 5 cities does not apply to 6, 7, . . N cities. Also any solution found applies to 5 specific cities. Changing the cities will require a new solution.

Man will never fly. Space travel is merely a dream. All aspirin is alike.