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.'"
Re:NP (Score:4, Informative)
Re:NP (Score:5, Informative)
Actually, NP stands for Non-deterministic Polynomial, i.e. An NP-complete problem can be solved in polynomial time in a nondeterministic Turing machine. In practice, this means that a candidate solution can be verified in polynomial time in a deterministic Turing machine (e.g. a normal computer). Normally this means the problem is exponential or factorial in a deterministic computer.
Now, NP-hard problems are those that are *at least* as hard as NP-complete, i.e. they need not be NP, so "polynomial verification" is not required.
Found the article on arxiv (Score:5, Informative)
"Determining dynamical equations is hard" by Toby S Cubitt, Jens Eisert, Michael M Wolf.
http://arxiv.org/abs/1005.0005 [arxiv.org]
An earlier article by same team:
"The Complexity of Relating Quantum Channels to Master Equations" by Toby S. Cubitt, Jens Eisert, Michael M. Wolf
(Submitted on 17 Aug 2009 (v1), last revised 12 Sep 2011 (this version, v2))
http://arxiv.org/abs/0908.2128 [arxiv.org]
Re:NP (Score:5, Informative)
NP = can be VERIFIED in polynomial time by a deterministic TM ('normal computer')
equivalently it can be SOLVED in polynomial time by a non deterministic TM.
This is different than problems solved in non-polynomial time (e.g: exponential time). While it is not known if NP != P (i.e: if NP is really harder than P, as assumed), it is known that EXP > NP. So problems that require exponential time are in fact 'harder' than NP problems.
However, it's important to notice that the article states that physics problems are NP-Hard, and not necessarily NP-Complete. The difference is vast, since an NP-Hard problem doesn't have to be in NP. It can in fact even be an undecidable problem. The halting problem is both undecidable and NP-Hard.
NP Does Not Stand For Non Polynomial (Score:5, Informative)
Every time complexity theory shows up on Slashdot about half the posts try to explain what P, NP, NP-Complete, and NP-Hard mean but fail horribly. I'm going to post this and hope it gets modded up, though I have my doubts.
Quick, rudimentary definitions:
P: Deterministic polynomial time. A problem is in P if there exists a deterministic polynomial time Turing machine that decides it.
NP: Non-deterministic polynomial time. A problem is in NP if there exists a non-deterministic polynomial time Turing machine that decides it. Note that deterministic polynomial time Turing machines are a special case of non-deterministic polynomial time Turing machines, so every problem in P is also in NP. NP DOES NOT STAND FOR NON-POLYNOMIAL! Half the posts on this article are going to say that NP stands for non-polynomial and that only exponential time algorithms exist for problems in NP, so I want to nip it in the bud immediately. If NP stood for non-polynomial then P != NP trivially. Another way of defining NP is to say that there exists a deterministic polynomial time verifier for every problem in NP. A deterministic polynomial time verifier is an algorithm that, given an instance of a problem and some extra piece of data (usually a potential answer), can decide the problem.
NP-Hard: A problem q is NP-Hard if there exists a polynomial time reduction from every problem in NP to q. Since reductions exist, if you found a deterministic polynomial time algorithm that solved q you would show that P = NP. Read up on Cook's theorem if you're interested in how arbitrary polynomial time reductions can be made from any problem in NP to Circuit-SAT (an NP-Complete problem).
NP-Complete: A problem is NP-Complete if it is both NP-Hard and in NP. There exist NP-Hard problems that are not NP-Complete.
Anyways, continue....
Re:NP (Score:5, Informative)
No, we don't know that yet (that's the whole P=NP debate). The thing we do know is that they can be solved non-deterministically in polynomial time.
Re:What ISN'T NP-Hard? (Score:4, Informative)
Perhaps unfortunately neither factoring or discrete log are known to be NP-hard yet (fortunately) polynomial time algorithms have thus far alluded us although BQP algorthims (Shor's algorithm) have been found. Of course an NP-hard problem in BQP would be a major discovery. Also simulation of quantum mechanical systems (protein folding) is known to be in BQP, although no polynomial algorithm is known and it isn't known to be NP-hard. While its true that a great many interesting problems that apparently aren't in P but are in NP are NP-hard, but the above are examples of important problems that aren't.
Re:NP (Score:4, Informative)
No, NP-**hard** problems are by definition no easier than the hardest problems in NP. It's an open question whether P = NP in which case all NP-hard problems that are also in NP (that intersection is known as NP-complete) are in P as well.
Re:NP (Score:5, Informative)
Attention: Car analogy in the last paragraph! Skip ahead, if you are bored.
If you can prove NP != P, then yes. In that case, you can not solve an NP-hard problem in polynomial time on a deterministic Turing machine. You can still solve it on a non-deterministic Turing machine in polynomial time though. And on an Oracle-NP machine, you can even solve it in one step; as those machines have an "Oracle" that can tell you the solution of an arbitrary problem in NP in one step.
There's a enormous zoo of complexities to sort problems into, from LOGSPACE, PSPACE, P, NP, PSPACE, NPSPACE, EXPSPACE, EXP, Oracle(P) all the way up to problems that are provably non-computable, like the Halting Problem.
But get this: All these categories have in effect a specific machine associated with them. For example PSPACE problems are those, that can be solved on a machine that needs a polynomial amount of memory based on the input size to solve a problem. LOGSPACE is the same, but with logarithmic space. CSPACE is the same with a constant amount of space.
Then you get to P, which does not care for space (indeed, the memory of the machine is assumed to be infinite), but it can only deterministically execute its program. If reading the symbol A in state B, it can only execute the action C -- and no other. If that machine can solve your problem in polynomial time (that is, polynomially many executions of operations with constant cost), then the problem is in P.
NP is the same, but now your machine may execute either action C or D when in State B and reading symbol A, depending on a certain random variable (i.e. a coin-flip). If it does not need more than polynomially many of those "random" steps, then your problem is in NP.
And now here's the nice thing: Every problem in P is also in NP. Why? Easy, because a non-deterministic machine can emulate a deterministic one; therefore, an NP-machine can trivially solve the problems a P-machine can by just following the same recipe (or emulating the P-machine).
But here's the difficult thing: Is it possible to create a P-machine that can emulate an NP-machine while still needing only a polynomial number of steps for each step of the NP-machine. After all, remember than n^c * n^d = n^(c+d). If both c and d is constant; (c+d) is constant and this n^(c+d) is still polynomial in respect to n.
The problem is, this reverse-question is damn hard to prove. But what you can prove is, is that there are certain problems whose solution on an NP-machine has a strange property: If you find a machine that can solve this problem on polynomial time, it can solve ALL OTHER NP-problems also in polynomial time; just by first rephrasing the desired problem to the problem it can actually solve. These problems are called NP-hard, because they are at least as hard as every other NP-problem. NP-complete problems are those whose results can be shown to be verifiable in P-time.
Thus, if you solve any NP-hard problem on a P-machine, you have shown that all NP-problems are solvable with that machine. If you can only show that the solved problem is in NP (but not -hard), then all you've shown is that the problem is a P-problem instead.
As always, if you want to known more, ask Wikipedia.
If you want a car-comparison, though, maybe that will do: There are cars and airplanes. Airplanes can provably fly, drive around and transport cars; we think that cars can only drive around and transport other cars (and some small airplanes). If you can show that you can make a flying car, that can transport any airplane, you have shown that airplanes are not more than just strange looking versions of cars.
Re:NP (Score:4, Informative)
Minor correction due to it being far too late over here for perfectly clear thinking:
NP-complete is actually a problem that solves all NP-problems (including NP-hard) and can be shown to be itself in NP. NP-hard removes the latter restriction, as any machine that can solve problems "harder than NP-complete" can trivially solve all NP-problems. So NP-hard encompasses more problems and is thus the broader category of problems. Please keep that in mind when reading my above posting, as its points are still correct, but showing P = NP-hard is much, much, much more difficult than showing P = NP-complete.
Of course, any single NP-hard problem might actually be "merely" an NP-complete one, in case we have just not yet found an algo that can execute it in NP-time.
Re:Metaphysics (Score:4, Informative)
Just because something is NP hard does not make it especially hard. NP-hard problems are only necessarily hard if the number of variables involved is high.