Can nature solve hard problems?

author: Marc Mézard, École Normale Supérieure (ENS)
published: Oct. 17, 2008,   recorded: September 2008,   views: 3707

Related Open Educational Resources

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.


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 page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 jugni, September 6, 2021 at 5:48 p.m.:

Cool, great explanation

Write your own review or comment:

make sure you have javascript enabled or clear this field: