A paper accepted for Physical Review Letters  is currently being credited with the claim that "Physics is NP hard". However, it all depends on what you mean by "Physics".

NP hard problems are a strange set because they are at least as hard as the NP complete problems, but they could be harder. The simple way of thinking of this is that they usually correspond to problems that would take just too long to solve for any real world version of the problem running on a real world computer. They generally involve some sort of combinatorial search for a solution that grows exponentially or faster as the number of items involved grows.

What the paper to be published claims to have proved is stated in its title, Extracting dynamical equations from experimental data is NP hard, and the abstract goes on to say:

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

So the procedure which is NP-hard is that you can observe the world in any amount of detail and then try to derive the equations that govern the dynamics. That this is NP hard shouldn't come as a huge surprise.

Although the paper isn't yet published in Physical Review Letters, there's a preprint in: arXiv:1005.0005v1.

Here the basic idea is explained. Take a general expression for the possible dynamics and deduce the parameters from snapshots of the system at various times. What you have is a problem where you are given the initial state s(0) and as many snapshots s(t) as you require. From this data you have to deduce the parameters of the master equation which is a search problem. A simpler form of the question illustrates why it so difficult. Given just one snapshot work out if it could have been generated by valid dynamics from the original state. Notice that this question just requires that you find a single equation that could have generated the time development - given we have only one snapshot there could be many. The problem becomes NP-hard because the forward calculation from equation to development involves e^x but going back the other way, i.e. from development to equation involves log x, which in the complex domain is multivalued. You have to search for the correct selection of values that give you the result.

It turns out that this search is equivalent to the 3SAT problem, which involves assigning a set of values to three variable in a logical expression to make it true. The 3SAT problem is NP-complete and so the task of finding the dynamics from the snapshots is NP-hard as 3SAT can be reduced to it in polynomial time but it is not necessarily in NP.

The argument holds for both classical and quantum systems, so deducing the equations from full data on a system is NP-hard.

Is this so surprising?

Probably not. After all, we have long been used to the idea that chaos is natural for dynamical systems. So why should be expect the data to supply the equations in an easy way? Systems with high degrees of symmetry, on the other hand, probably do admit an easy algorithm when it comes to deducing there dynamics.

It is nice to see that computer science and complexity theory in particular has something to say about physics.

More information

Determining dynamical equations is hard Toby S. Cubitt, Jens Eisert, Michael M. Wolf arXiv:1005.0005v1

Extracting dynamical equations from experimental data is NP hard Toby S. Cubitt, Jens Eisert, Michael M. Wolf

Related Articles

Computational Complexity

Computability

Pancake flipping is hard - NP hard

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.