Physics and NP-complete Problems
Speaker: Dr. Scott Aaronson, (speaker organisation unavailable)
When: 2005-12-16 12:00:00
Venue: Building 7 (Parnell) Rm 222
Host: (seminar host unavailable)
Abstract:Many optimization problems belong to a class known as the
NP-complete problems, which computer scientists believe are
essentially intractable. Examples of such problems include the
travelling salesman problem and finding the ground state of a spin
glass.
Remarkably, however, there are many physical systems which appear at
first glance able to solve such problems efficiently. I'll survey
proposals including soap bubbles, protein folding, quantum
computing, quantum advice, quantum adiabatic algorithms,
quantum-mechanical nonlinearities, hidden variables, relativistic
time dilation, analog computing, Malament-Hogarth spacetimes,
quantum gravity, closed timelike curves, and 'anthropic computing.'
While I don't believe any of the proposals will let us solve
NP-complete problems efficiently, I'll argue that by studying them,
we can learn something not only about computation but also about
physics.
Biography:(biography unavailable)
Type: Physics Colloquium Series 2005
Contact:(seminar host unavailable), seminar host ((office@itee.uq.edu.au))
or Guido Governatori (ITEE seminar co-ordinator)
(guido@itee.uq.edu.au)