DPG Phi
Verhandlungen
Verhandlungen
DPG

Regensburg 2002 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

DY: Dynamik und Statistische Physik

DY 17: Kritische Ph
änomene und Phasenumwandlungen II

DY 17.1: Talk

Monday, March 11, 2002, 16:15–16:30, H3

Statistische Mechanik harter erfüllbarer SAT-Probleme — •Wolfgang Barthel1, Martin Weigt1 und Alexander Hartmann21Institut 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

100% | Mobile Layout | Deutsche Version | Contact/Imprint/Privacy
DPG-Physik > DPG-Verhandlungen > 2002 > Regensburg