Physics Is (NP-)Hard

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.'"

Comments

No problem

[Anonymous Coward]

I am NP-smart

Re:No problem

[Zero__Kelvin]

Not Particularly?

Well no wonder I failed physics

[the_humeister]

I always thought it was hard, but that takes it to another level

Re:NP

[Samantha Wright]

In case this actually slips anyone up: NP-hard means that, given a large number of options, and an answer that is a certain combination or ordering of those items, every possible combination or ordering must be evaluated to figure out the correct answer. "NP" stands for "non-polynomial," e.g. an exponential or factorial function of the number of items used.

Ow, my brain

[Walt Sellers]

It seems it is nearly NP-Hard to understand the concept of "NP-Hard". Thanks to Wikipedia I now understand that I don't fully understand this.

I should think that turning observations into accurate equations is hampered by never knowing if you have enough of the correct observations to determine the correct equation.

Re:NP

[timmy.cl]

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.

Hmm...

[tool462]

So these scientists were studying the science of physics itself, at some higher abstract level.
Does that mean this research is metaphysics?

Found the article on arxiv

[mattr]

"Determining dynamical equations is hard" by Toby S Cubitt, Jens Eisert, Michael M Wolf.
http://arxiv.org/abs/1005.0005

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

Here, we give complexity-theoretic solutions to both these open problems which lead to a surprising conclusion: Regardless of how much information one has gained, deducing dynamical equations is in general an intractable problem -- it is NP-hard. More precisely, the task of determining dynamical equations in general is equivalent to solving the (in)famous P versus NP problem [1]. If P != NP, as is widely believed, then there cannot exist an efcient method of deducing dynamical equations.

On the positive side, our work leads to the rst known algorithms for extracting dynamical equations from measurement data that are guaranteed to give the correct answer. For systems with few degrees of freedom, this is immediately applicable to many current experiments. And, indeed, the primary goal of many experiments is to characterize and understand the dynamics of a system.

Re:NP

[Anonymous Coward]

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

[Anonymous Coward]

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

[siride]

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:NP

[Jappus]

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.