Can nature solve hard problems?
published: Oct. 17, 2008, recorded: September 2008, views: 3704
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Nature certainly poses a lot of hard problems to the physicist or the chemist.But can natural systems, or nature-inspired artifacts, be used to solve hard problems? This general question can be made a bit more precise by focusing on combinatorial optimization problems. Simple attempts at solving problems like Hamiltonian path or Steiner tree seem far from the goal, and in many case it seems that the occurence of a glassy transition, which freezes the relaxation in metastable states, is the major obstacle. Recently, some of the hardest constraint satisfaction problems have been addressed successfully through message passing methods, with algorithms which partly get around the freezing transition. The talk will review this approach and discuss its limitations. Message passing, which is a purely local strategy based on the exchange of simple probabilistic messages along a graph of constraints, is not only very powerful, but also appealing since its basic ingredients share some similarity with neural networks. This points to alternative, ``natural'' ways of solving hard problems, through artifacts which get around the basic physical limitations of usual thermal systems.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !