Glassy phases: a possible origin of computational hardness

Given a large set of discrete variables, and some constraints between them, is there a way to choose the variables so that all constraints are satisfied? This ``satisfiability'' problem is one of the most fundamental complex optimization problems. It also has very concrete applications, for instance in computer chip testing, or in error correcting codes. The study of random satisfiability problems has shown that the hardest instances are obtained in some range of parameters where a phase transition to a glass phase takes place. Taking satisfiability as an example, this talk will summarize some of the recent progress obtained in this field using statistical physics concepts and methods which originate in the study of spin glasses. It will discuss in particular the emergence of glass phases, how they are responsible for a dramatic slowdown of algorithms, and how analytic insight into this glassy nature can help to design new types of algorithms which solve very large constraint satisfaction problems.