Berechnungskomplexität und Statistische Mechanik

Die algorithmische Komplexität von Entscheidungs- oder Optimierungsproblemen ist normalerweise Gegenstand der Informatik. Dort konzentriert man sich allerdings auf die Analyse des schlechtesten Falles (worst case analysis). Die Eigenschaften typischer, zufälliger Probleminstanzen weichen davon jedoch zum Teil beträchtlich ab. Hier kommt die statistische Mechanik ins Spiel, die sehr mächtige mathematische Werkzeuge zur Analyse von Systemen mit Unordnung (Zufallsinstanzen) entwickelt hat. Wir haben unter anderem mit diesen Methoden erstmals exakte Resultate für eines der wichtigsten Probleme der Informatik, dem Satisfiability Problem, erhalten.