10. Nov. 2016, 16:15 Uhr, Gebäude NW1, Raum H3
Habilitations-Kolloquium: Phase-transitions in algorithms: the connections between statistical physics and theoretical computer science
Dr. Tiago Paula Peixoto, ITP, Univ. Bremen
A central part of theoretical computer science deals with establishing the complexity of problems that can be solved with computers. In this context, an important distinction can be made between "easy" problems, for which answers can be produced in time comparable to what is required to verify them, and harder ones where, although the answers can be verified rapidly, there are no known algorithms that can yield them in reasonable time. Often, it is not obvious whether a problem is truly hard, or if we only haven't found an easy solution yet. Indeed, an outstanding theoretical problem is to understand in general what fundamentally distinguishes a hard problem from an easy one. In this talk, I will highlight an interesting aspect to this problem that comes from employing analytical methods from statistical physics. Namely, it has been discovered that the solution space of putative hard problems share a phenomenology common to granular or glassy materials, and undergo a phase transition between an "easy" phase, where solutions can be found in short time, and an impossible phase, where no solutions exist. It is only close to the boundary between the two phases that the time required to find solutions diverge. This phenomenon not only sheds new light in an important problem in mathematics and computer science, but reveals a deep connection between physics and computation.
During the talk I will focus on paradigmatic NP-complete problems such as Boolean constraint satisfaction and integer partitions, and how they can be analyzed using methods developed originally for spin glasses.