Scott Aaronson has a cool article (PDF) that looks at half a dozen proposed ways of solving really difficult computational problems—such as using soap bubbles or black holes, or time-traveling, or playing Russian roulette.
The paper is playful but serious—a serious survey of the far-out. A lot of it is mathematical gibberish to me, but it's amusing all the way through, and there's a fun “think big—no bigger than that” section at the end.
I have one super-geeky nitpick, though:
Even many computer scientists do not seem to appreciate how different the world would be if we could solve NP-complete problems efficiently. I have heard it said, with a straight face, that a proof of P = NP would be important because it would let airlines schedule their flights better, or shipping companies pack more boxes in their trucks! One person who did understand was Gödel. In his celebrated 1956 letter to von Neumann (see [69]), in which he first raised the P versus NP question, Gödel says that a linear or quadratic-time procedure for what we now call NP-complete problems would have “consequences of the greatest magnitude.” For such an procedure “would clearly indicate that, despite the unsolvability of the Entscheidungsproblem, the mental effort of the mathematician in the case of yes-or-no questions could be completely replaced by machines.”
But it would indicate even more.... [Ed.: color added]
Here Scott shifts carelessly between two completely different hypotheticals (blue and orange). The statement he lambasts, that P=NP would be important for logistics, is actually an overstatement. A proof that P=NP (blue) almost certainly would have no practical consequences at all, unless I'm wildly mistaken, because a great many problems in P are not practically solvable. Who cares if every problem that can be solved in O(2n) time can also be solved in O(n1000000) time? In practice the latter is probably worse.
By contrast, a discovery that NP-complete problems can be solved in quadratic time (orange) would be a mind-blowing, probably world-changing event. But this is unlikely in the extreme.
2 comments:
> Who cares if every problem that can be solved in O(2n) time can also be solved in O(n1000000) time? In practice the latter is probably worse.
Depending on the problem size and computer speed.
Not really. For problem size n=2, n^1000000 is approximately one googol to the 3000th power. No computer can do anything that many times. I don't think it's even possible in principle, unless there are yet-unknown loopholes in the laws of physics.
For the sake of comparison, the observable universe contains less than one googol atoms. The age of the universe is maybe 10^17 or 10^18 seconds.
Post a Comment