Students and researchers alike have long understood that physics is challenging. But only now have scientists managed to prove it. It turns out that one of the most common goals in physics—finding an equation that describes how a system changes over time—is defined as "hard" by computer theory. That's bad news for physics students who hope that a machine can solve all their homework problems, but at least their future jobs in the field are safe from automation.
Physicists are often interested in mathematically describing how a system behaves: for instance, a formula tracks the motions of the planets and their moons in their complicated dance around the sun. Researchers work out these equations by measuring the objects at various points in time and then developing a formula that links all of those points together, such as filling in a video from a set of snapshots.
With each new variable, however, it becomes tougher to find the right equation. Computers can speed things up by sifting through potential solutions at breakneck speed, but even the world's top supercomputers meet their match with a certain class of problems, known as "hard" problems. These problems take exponentially more time to solve with every additional variable that is thrown into the mix—an extra planet's motion, for instance.
Sometimes, hard problems can be made easier through clever mathematical maneuvering, but quantum physicist Toby Cubitt of the Complutense University of Madrid and colleagues have stamped out that hope for physics equations that describe a system through time.
Mathematicians recognize a set of truly hard problems that can't be simplified, Cubitt explains. They also know that these problems are all variations of one another. By showing that the challenge of turning physics data into equations is actually one of those problems in disguise, the team showed this task is also truly hard. As a result, any general algorithm that turns a data set into a formula that describes the system over time can't be simplified so that it can run on a computer, the team reports in an upcoming issue of Physical Review Letters.
The physics equations are in good company, according to computer scientist Stephen Cook of the University of Toronto in Canada, who was not involved in the work. "Literally thousands of problems" fall into this category of truly hard problems, he says.
There's still a shred of hope that physicists will find a way to turn these supposedly unsimplifiable problems into computer-solvable forms. If such an easier route were to turn up, profound knock-on effects would ripple through mathematics because it would mean all the other hard problems could be simplified as well. The Clay Mathematics Institute in Cambridge, Massachusetts, offers a $1 million prize to anyone who discovers such a universal problem-tenderizer.
Mathematicians, however, strongly suspect that it can't be done (although the Clay Institute will also pay you $1 million for proving that suspicion true). In that case, "there is no smarter way" for computers to work out these physics equations "than brute-force checking" of each possible equation, Cubitt says. Still, he muses, if computers find these equations so difficult to figure out, why have physicists been able to calculate so many of them?
Physicist Heinz-Peter Breuer of the University of Freiburg in Germany suggests it's because physicists give their brains—and their computers—a head start. They set the stage with the laws of physics that have already been developed by the likes of Newton, Maxwell, and Einstein, and this gives the outline of the equation, he says. The experimental data only have to fill in the details. Physics may be tough for computers, but real scientists get around it by standing on the shoulders of giants.