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.'"
Comment removed (Score:3, Insightful)
What ISN'T NP-Hard? (Score:4, Insightful)
Aren't all except the most basic algorithms, up to and including polynomials, NP-Hard? I know the term's meaning, but stories about proving things are NP-Hard seem sort of useless to me. The English language, for example, is NP-Hard. Has this been proven? I don't know, frankly, I don't care, but it's easy to understand that it must be considering it evolves and changes as one analyses it... Much like any quantum or physical system, or even the English themselves.
Determining if something is NP-Hard, is... wait for it.... wait for it... NP-Hard!
Re:NP (Score:4, Insightful)
Congratulations, you're the first respondent to not correct "non-polynomial" as "non-deterministic polynomial." (Personally I blame lazy professors.)
There are lots of problems solvable by a deterministic Turing machine in polynomial time (I.e. problems known for certain to be in P) that still need unique solutions for each possibility, though. Think about searching a list: you have to go through every item until you find the right one; there's no way to do it that's easier. The point about the traveling salesman problem and other classic NP-hard (and their best friends, NP-complete) challenges is that you are working with finding combinations of items, and you must check all possible combinations; there is no easier way. We haven't proven that there's no easier way (and not due to lack of trying, mind you), but there aren't a lot of people who seriously believe we'll find one.