Physics Is NP Hard
Physics Is NP Hard
Written by Mike James   
Saturday, 25 February 2012

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 ex 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 turn 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-hard and so the task of finding the dynamics from the snapshots is also NP-hard.

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


Pancake flipping is hard - NP hard



blog comments powered by Disqus


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.


Actions On Google

Google has opened up Actions on Google, its developer platform for Google Assistant. It can now be used to add Conversation Actions that provide a way to give your users information, services, an [ ... ]

ReSharper Adds Support For C#7

The latest release of ReSharper has added support for  Visual Studio 2017 RC, C# 7 and VB.NET 15.

More News

Last Updated ( Saturday, 25 February 2012 )

RSS feed of news items only
I Programmer News
Copyright © 2017 All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.