[Colloquium] REMINDER: today's lecture by Scott Aaronson at 12:30 p.m.

[Margery Ishmael]

DEPARTMENT OF COMPUTER SCIENCE
Lecture of general interest to science


Title: Computational Intractability as a Law of Physics
Speaker: Scott Aaronson (University of Waterloo)

Date: Wednesday, March 7
Time: 12:30 pm
Place: Ryerson 251

ABSTRACT

Several of the deepest principles in physics can be seen as limits on
technology: for example, the Second Law of Thermodynamics and the
impossibility of superluminal communication.  In this talk, I'll ask
whether the hardness of NP-complete computational problems would
likewise be useful to assume as a physical principle.  To investigate
this question, I'll study the computational effects of living in a
universe with closed timelike curves, a universe where the Schroedinger
equation was nonlinear, a universe with particular many-particle
entangled states left over from the Big Bang, or a universe where you
could kill yourself with some probability and then 'postselect' on
remaining alive.  I'll show that one can make definite, nontrivial
statements about what problems could be efficiently solved in each of
these universes -- and also about what problems still couldn't be.

-------------

Host: Laci Babai   773-702-3486   laci at cs.uchicago.edu


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070307/24885ed1/attachment.htm