Computer scientists study game theory from the perspective of computability.
Daskalakis, working with Christos Papadimitriou of the University of California, Berkeley, and the University of Liverpool’s Paul Goldberg, has shown that for some games, the Nash equilibrium is so hard to calculate that all the computers in the world couldn’t find it in the lifetime of the universe. And in those cases, Daskalakis believes, human beings playing the game probably haven’t found it either.
Solving the n-body problem is beyond the capabilities of the world’s smartest mathematicians. How do those rocks-for-brains planets manage to do pull it off?
Cheap Talk 
11 comments
Comments feed for this article
November 10, 2009 at 10:18 pm
gappy
Jeff, I don’t know if your comment was tongue-in-cheek, but your observation has deep historical precedents. In the early 19th century mathematicians just didn’t have the tools to tackle existence and uniqueness of complex PDEs, including Gauss’ law. If I remember correctly [1], Gauss was addressing the issue in front of his students by showing electrostatic equilibria with a charged metallic body. Nature has a way to solving problems that were and are beyond our reach. I am not too sure about humans, though.
[1] I must have read this in Jackson’s Classical Electrodynamics, or maybe one of Feynman’s lectures.
November 11, 2009 at 3:06 am
noamnisan
The n-body problem can easily be computed in the sense of being simulated by a computer in a way that will produce the same results as nature does.
It doesn’t have a closed form solution, and some questions like “what will happen eventually cannot be solved efficiently by computers but neither can nature do so.
There is nothing that nature can do regarding the n-body problem, and in fact all other physical phenomena, that computers can’t. The only known exception seems to be some quantum phenomena which required “quantum computers” rather than “classical ones”.
November 11, 2009 at 8:42 am
jeff
Noam, thank you these are helpful clarifications.
I am making the observation that planets have no brains and from the beginning of time they have been doing things that people with very large brains cannot do and that computers were not able to do until very recently.
This must mean that computing power is not necessarily a constraint on what can be done.
No doubt there are cases where it is a constraint on what people can do, probably the typical case. But the same argument suggests that the trade-offs implied by modeling this constraint in terms of computability do not necessarily relate in any useful way to the actual trade-offs that naturally occurring brains face.
Still, its the best model we’ve got and we should do what we can with it. (And of course economics and game theory are prone to analagous criticisms.)
November 12, 2009 at 5:30 am
Robert Johnson
“…neither can nature do so.” What do you mean?
November 11, 2009 at 5:22 am
Robert Johnson
noamnisan,
Could you explain in a little more detail or provide a link? I’d really like to understand better.
November 11, 2009 at 11:42 pm
mike
To simulate it on a computer, and I suppose in real life, you divide time into frames and just iterate; you keep on moving the bodies bit by bit using newton’s second law.
Basically you’re solving the integral by actually doing the sum, instead of using fancy calculus. So the difficulty is not in finding the actual answer, but figuring out a formula that can give you the answer without having to use such a brute force method.
November 12, 2009 at 5:33 am
Robert Johnson
Thanks, Mike. I remember reading something about doing the calculation iteratively. I was puzzled by the comment “what will happen eventually cannot be solved efficiently by computers but neither can nature do so.” Doesn’t nature solve that problem?
November 12, 2009 at 5:57 am
noamnisan
What will happen in time X can be simulated well. Questions that ask about an unlimited amount of time in the future (like “will these two bodies ever collide?”) may be hard to answer without doing the simulation for the amount of time until a collision — which may be infeasible — just like in nature.
November 12, 2009 at 6:05 am
noamnisan
I’m not really sure what a good online reference is. Perhaps the introduction to http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf although that paper focuses exactly on the quantum issue that requires quantum computers.
November 13, 2009 at 11:19 am
Walt
I’m a big fan of your blog, but this is an embarrassing misreading. This is a deliberate decision on your part to ignore a discovery inspired by another field because it’s somehow inconvenient for your world-view. The n-body problem is not NP-complete. Numerically solving the behavior of heavenly bodies is no big mystery — Gauss calculated the orbit of Ceres by hand in the 19th century.
There are no known practical physical processes that can solve NP-complete problems quickly. Quantum computing is hot right now because it it offers the prospect of solving some problems that are now intractable (such as integer factorization). But even there as far as we know even if we manage to build quantum computers (itself a major research effort) that NP-complete problems still remain intractable.
November 27, 2009 at 1:43 pm
Economists and Complexity « Algorithmic Game Theory
[…] mostly don’t care since they see equilibrium reached everyday, contrary to what CS says. As Jeff Ely quips: “Solving the n-body problem is beyond the capabilities of the world’s smartest […]