## Physics Is (NP-)Hard 212

Posted
by
Soulskill

from the assume-a-spherical-traveling-salesman dept.

from the assume-a-spherical-traveling-salesman dept.

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.'"*
## NP-HARD Mapping (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

notcorrect "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

combinationsof items, and youmustcheck 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.