Computers’ inability to find physical laws is a clue to math’s relationship to reality

For some people, all math problems are difficult.

But for computer scientists, most math problems are easy. The computer does all the work.

Sometimes, though, problems come along that even computers can’t handle. Even the most powerful supercomputers on the planet can gag on certain types of mathematical puzzles. Computer scientists have a special term to describe such problems. They’re called “hard.”

Physicists, of course, know all about hard problems, such as figuring out the laws of nature. That task is a bit different, though. Instead of solving an equation, it’s finding an equation — figuring out what formula accurately describes past and future experimental observations. You know, dropping cannonballs off of buildings, or watching planets amble through the skies, and using that data to compose an equation to predict how all matter moves when subjected to forces. Try giving that problem to a computer.

OK, some scientists have given similar problems to computers, such as one named Eureqa, as Rachel Ehrenberg reported in a recent issue of Science News. But it turns out that in general, computers can’t extract the exactly correct equation for describing data from observing a system unless the system is ridiculously simple. To use technical language again, the equation-finding problem is hard. Or even more technically, it’s “NP hard.”

“Regardless of how much information one obtains through measuring a system, extracting the underlying dynamical equations from those measurement data is, in general, an intractable problem,” physicists Toby Cubitt, Jens Eisert and Michael Wolf write in a recent issue of Physical Review Letters.

Curiously, the physicists make this case by first proving that it is in fact possible to design a step-by-step process allowing a computer to find an equation that describes a system — if the system is small and simple enough. But making a system just a little bigger and more complicated makes it a lot harder to find the equation. When problems get harder much more rapidly than they get bigger, a computer will eventually choke on them — or as experts would say, the computer can’t solve the problem “efficiently.”

Problems that a computer can solve “efficiently” (that is, fast enough to get the answer before the universe goes dark) are labeled P. Problems for which the answer can be checked by a computer (after you’ve looked the answer up in the back of the book) are called NP. Solving the equation-finding problem would mean you’d know how to solve all NP problems, which, by definition, makes the equation problem NP hard.

Most mathematicians are pretty sure that among the NP problems (those whose answer can be checked by a computer) there are some that cannot be solved efficiently by an ordinary computer. (In other words, P does not equal NP.) But if a computer can find the equation that correctly describes experimental data, then P must equal NP, Cubitt, Eisert and Wolf demonstrate. So unless by some miracle P = NP after all, it’s hopeless to search for an algorithm that finds the mathematical laws of nature for you.

But wait a minute. How, then, do humans do it? Physicists seem to have been able to find all sorts of equations that accurately describe the experimental data encountered in nature. Maybe humans can find equations that are only approximately correct, such as those produced by computers like Eureqa. But Cubitt, Eisert and Wolf speculate that nature somehow has arranged to keep things simple to make science possible.

“Experience would seem to suggest that, while general classical and quantum dynamical equations may be impossible to deduce from experimental data, the dynamics that we actually encounter are typically much easier to analyze. Our results pose the interesting question of why this should be, and whether there is some general physical principle that rules out intractable dynamics,” they write.

On the other hand, maybe there’s something special about people, not nature, that allows them (some of them, anyway) to deduce mathematical laws that nature must obey. Great scientists have historically been able to construct squiggles on paper that predicted the outcomes of experiments that had not yet been performed. Dirac’s math revealed the existence of anti­matter before it was found in cosmic rays. Einstein’s equations foretold the existence of black holes. Equations from half a century ago have been deemed worthy of spending billions of dollars to hunt for the Higgs boson.

Somehow, mathematical abstractions deduced by human minds resonate with the behavior of the physical universe. No doubt this miracle has something to do with the fact that brains are physical computers that evolved under the constraints imposed by nature’s laws. If ordinary computers really can’t solve some of the math problems that human brains can, then, perhaps that means there’s more to be discovered about math’s relationship to physical, and biological, reality.

SN Prime April 16, 2012 | Vol. 2, No. 15