Regensburg 2002 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe
DY: Dynamik und Statistische Physik
DY 17: Kritische Ph
änomene und Phasenumwandlungen II
DY 17.1: Vortrag
Montag, 11. März 2002, 16:15–16:30, H3
Statistische Mechanik harter erfüllbarer SAT-Probleme — •Wolfgang Barthel1, Martin Weigt1 und Alexander Hartmann2 — 1Institut für Theoretische Physik, Bunsenstr.9, 37073 Göttingen — 2Ecole Normale Supérieure, 24 Rue Lhomond, 75231 Paris Cedex 05, Frankreich
Die zufällige Erzeugung von kombinatorischen Problembeispielen mit vorgegebenen, aber für Fremde schwer rekonstruierbaren Lösungen ist ein fundamentales Problem der theoretischen Informatik. Es hat wichtige Anwendungen in der Kryptographie (z. B. PIN, Datenverschlüsselung) und bei der Generierung harter Testbeispiele für numerische Algorithmen.
Auf Grundlage einer Formulierung als Modell der statistischen Mechanik schlagen wir einen Generator für harte erfüllbare Instanzen des Erfüllbarkeitsproblems (SAT) vor [1]. Die Erzeugung der härtesten Instanzen beruht auf der Existenz eines ferromagnetischen Phasenübergangs 1. Ordnung und der Glasartigkeit angeregter Zustände. Die analytischen Vorhersagen werden durch numerische Simulationen mit verschiedenen kombinatorischen Algorithmen untermauert.
[1] W. Barthel, A.K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt und R. Zecchina, preprint cond-mat/0111153