A large number of problems we deal with in computer science are considered hard. One such problem is the Satisfiability Problem (SAT). Despite years of work, no one has developed algorithms for SAT that can solve all possible instances in a reasonable amount of time. In fact, most researchers do not believe any such algorithm exists. In practice, SAT-solvers are either complete solvers that always solve the problem and sometimes run in a reasonable amount of time or incomplete solvers that always run in a reasonable amount of time and sometimes solve the problem.

Recently, a group of physicists have applied techniques of statistical mechanics to problems such as SAT to gain more insight into why the problems are hard. As part of their work, they have proposed a new algorithm called Survey Propagation that seems to work better than other current incomplete solvers.

This talk will highlight the current state of the research and expose reasons why this new algorithm works well and reasons why it may fail in some important situations.