2008 Woodie Awards
Aaronson returns to give academic lecture
Jeff Ward
Issue date: 11/19/07 Section: News
- Page 1 of 1
Scott Aaronson returned to Clarkson University to give his talk last Tuesday on "Computational Intractability as a Law of Physics." Aaronson was last at Clarkson in 1997 as a 15-year-old Clarkson School student. In his single year here, before attending undergraduate at Cornell, he published a paper in the ACM Proceedings. The talk he gave on Tuesday contained elements from math, computer science, and physics.
The talk's theme was "The No Super-Search Principle," or, as Aaronson called it, "The laws of physics don't let us find a needle in a haystack without sifting through lots of hay." Aaronson's talk was giving evidence for the nonexistence of "über-computers" as a physical law, much the same way we know we cannot have warp drives or perpetual motion machines. In order to explore this, Aaronson needed some computer science principles such as P, NP, and NP-Complete problems. P is a class of problems that can be solved easily on a computer like taking matrix determinants. NP problems are hard to solve but easy to check, like factoring two numbers. It is easy to multiply two numbers that are given to us and check to see what the answer is. A huge issue is whether P=NP. You may have heard that proving (or disproving) this is worth one million dollars from the Clay Institute. NP-Complete problems are those NP problems that if one of them is actually P, all of NP=P. Aaronson's intuition on this is that P and NP are not equal. He mentioned that if P=NP, it would be like saying "anyone who can appreciate a good symphony is Mozart," or "anyone who can check the steps of a hard proof is Gauss."
Throughout the rest of the talk, Aaronson explored whether quantum computers can solve NP-Complete problems. We know they can factor, but that is only NP, not NP-Complete. One technique was relativity computing.Start your computer, leave Earth near the speed of light, and return. Many years should have passed on Earth, but only a few hours have passed for you. A similar approach would be to go near the event horizon of a black hole where time slows down for you. These two approaches give quantum computers virtually limitless time to solve NP-Complete problems. Relativity computing requires too much energy to be feasible though.
There were more approaches like if the Schrödinger Equation was nonlinear, we could easily manipulate quantum states to solve NP-Complete problems in P. Aaronson said this should be taken as evidence that the Schrodinger Equation is linear. He also mentioned Zeno computing; halve the amount of time each computational step takes on each subsequent step. The problem is that our understanding of the world breaks down below the Planck scale (10-43 seconds). Aaronson concluded that the "NP hardness assumption will eventually be seen as analogous to the Second Law of Thermodynamics." To see everything he covered, Aaronson's slides can be found at his webpage http://www.scottaaronson.com.
The talk's theme was "The No Super-Search Principle," or, as Aaronson called it, "The laws of physics don't let us find a needle in a haystack without sifting through lots of hay." Aaronson's talk was giving evidence for the nonexistence of "über-computers" as a physical law, much the same way we know we cannot have warp drives or perpetual motion machines. In order to explore this, Aaronson needed some computer science principles such as P, NP, and NP-Complete problems. P is a class of problems that can be solved easily on a computer like taking matrix determinants. NP problems are hard to solve but easy to check, like factoring two numbers. It is easy to multiply two numbers that are given to us and check to see what the answer is. A huge issue is whether P=NP. You may have heard that proving (or disproving) this is worth one million dollars from the Clay Institute. NP-Complete problems are those NP problems that if one of them is actually P, all of NP=P. Aaronson's intuition on this is that P and NP are not equal. He mentioned that if P=NP, it would be like saying "anyone who can appreciate a good symphony is Mozart," or "anyone who can check the steps of a hard proof is Gauss."
Throughout the rest of the talk, Aaronson explored whether quantum computers can solve NP-Complete problems. We know they can factor, but that is only NP, not NP-Complete. One technique was relativity computing.Start your computer, leave Earth near the speed of light, and return. Many years should have passed on Earth, but only a few hours have passed for you. A similar approach would be to go near the event horizon of a black hole where time slows down for you. These two approaches give quantum computers virtually limitless time to solve NP-Complete problems. Relativity computing requires too much energy to be feasible though.
There were more approaches like if the Schrödinger Equation was nonlinear, we could easily manipulate quantum states to solve NP-Complete problems in P. Aaronson said this should be taken as evidence that the Schrodinger Equation is linear. He also mentioned Zeno computing; halve the amount of time each computational step takes on each subsequent step. The problem is that our understanding of the world breaks down below the Planck scale (10-43 seconds). Aaronson concluded that the "NP hardness assumption will eventually be seen as analogous to the Second Law of Thermodynamics." To see everything he covered, Aaronson's slides can be found at his webpage http://www.scottaaronson.com.
Be the first to comment on this story