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.
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.
To find out more about the forthcoming AI With the Best online event we talked with Ian Goodfellow who is one of the event's keynote speakers. We also took the opportunity to find out more about his a [ ... ]