It is a usual complaint of students the one about physics being hard, and now it is official, at least it is so from the computational complexity point of view. In a paper published in Physical Review Letters, researchers from Madrid, Berlin and Munich explore the difficulty in extracting the equations that dictate the evolution in time of a physical system from observations. In other words, you observe the world in any desired detail and then try to obtain the equations that govern the dynamics of the system. The authors show that this procedure is and NP-hard problem.

In computational complexity, P is a complexity class that contains all decision problems that can be solved by a deterministic Turin machine using a polynomial amount of computation time (upper bounded by a polynomial expression in the size of the algorithm). These problems can be thought of as tractable or feasible. The NP class (or nondeterministic polynomial) is the set of decision problems for which the answer can be verified in polynomial time. The problem of P v NP (whether N=NP or not) is one of the most important unsolved problems in computer science today.

Now, according to the article Physics (or dynamics) is an NP-hard problem. So what is that? Well, a problem is NP-hard is an algorithm for solving the problem can be transformed into one for solving any NP problem. This means that an NP-hard problem is as hard as any other NP-problem, or even harder.

What does this all mean for physics and physicists? Well, physicists are interested in describing mathematically how a system behaves – think of the motion of plants around the Sun or the displacement of a car along a motorway. The equations are worked out by measuring or observing the objects at various different times and then a formula is developed. With each new variable observed, it becomes more difficult to find the right set of equations. One might think that with computers (or supercomputers) this task could be automated. Nonetheless, these supercomputers meet their match with NP-hard problems as it would take exponentially more time to solve them with every extra additional variable added. The paper can be downloaded from the arXiv.

In any case, although physics turns out to be NP-hard, it is still lots of fun.