Komplexität und Phasenübergänge
Automatic Problem SolvingInstitut für Informatik
Universität Potsdam WS 05/06Thomas Hofmann
2
Komplexität
• Ressourcenaufwand (Rechenschritte oder Speicherplatzbedarf) des
besten Algorithmus für ein gegebenes Problem
• wächst mit Länge der Eingabegrösse n, aber wie? Skalierbarkeit
• Polynomialzeit: was rechentechnisch praktisch möglich ist
• Einteilung in Komplexitätsklassen
• wichtigste Frage der Komplexitätstheorie NP≠P
3
Satz von Cook
• SAT ist NP vollständig
• alle Probleme aus NP lassen sich in polynominaler Zeit auf das
SAT-Problem reduzieren
Beweisidee
• NP-Probleme sind auf einer nichtdeterministischen Turing-Maschine
in polynominaler Zeit lösbar
• Turing-Maschine durch aussagenlogische Formeln beschreiben
• ist genau dann erfüllt wenn die Maschine eine Lösung findet
• Konstruktion geht in Polynominalzeit
4
Beweismethode
• DNF A = p v Q v S
• Q : zu jedem Zeitpunkt kann es nur einen aktiven Zustand geben
• S : jedes Feld kann nur ein Symbol aufnehmen
• p : ist wahr wenn ein Feld zu einem bestimmten Zeitpunkt ein
bestimmtes Symbol enthält
• B,C,D : setzen p,Q und S durch
• E : sorgt für richtige Startbedingungen
• F,G,H : sorgen dafür das die Werte richtig aktualisiert werden
5
NP = P ?
• P Probleme sind mit deterministischen Turing Maschinen
in p. Zeit lösbar, NP nichtdeterministisch in p. Zeit lösbar
• P ≤ NP aber ist auch P ≥ NP?
• wenn ein Problem aus NP in P, dann alle
• NP-vollständige Probleme lassen sich vermutlich nicht
effizient lösen
6
Phasenübergänge
Motivation:
• Goldberg(1979); SAT ist im Durchschnitt in O(n²) lösbar
• NP: worst case scenarios
• Bestimmung von „average cases“ and „hard cases“
• Qualität des Generierungsverfahren der Formelmenge
und deren Bezug zu realen Problemen
• analytisch ist es nicht beweisbar, (n → ∞)
7
Generierungsverfahren
• Formellänge K, Zeilen M, Variablen N, Zeilen / Variablen c
• zufällig generierte Formeln in CNF
• random K-SAT
• random mixed-SAT
• costant probability model (P)
• random [k,l]-SAT
• kritischen Wert für c (L/N)
• Davis-Putnam procedure
8
easy-hard-easy pattern and over- / underconstrained
„the hardest area for satisfiability is near the point where 50% of the formulars are satisfiable“ [4] S.461
9
SAT-Solver mit konstanter Formellänge
10
3-SAT mit unterschiedlicher Variablenanzahl
11
Schlussfolgerung
• scharfe Transition bei der Erfüllbarkeitsfrage
• an diesem Übergang liegen die schwerstlösbaren
Probleme
• Schwierigkeiten bei gemischter Klausellänge
• crossover-point
• Übertragbarkeit der Ergebnisse auf andere SAT-Solver
12
Quellen- und Abbildungsverzeichnis
• [1] Stephen A. Cook; „The complexity of Theorem-Proving Procedures“; 1971• [2] Ian P. Gent and Toby Walsh; „The SAT Phase Transition“;1994• [3] David G. Mitchell and Hector J. Levesque; „Some Pitfalls for Experimenters
with Random Sat“; 1995• [4 ] David G. Mitchell, Bart Selman and Hector J. Levesque; „Hard and Easy
Distributions of SAT Problems“; 1992• Internetquellen: www.wikipedia.org;
www.grundstudium.de;
http://users.informatik.haw-hamburg.de/~voeller/th/thinf/node32.html
Abbildungen: S.9 und S.10 [3] S S.4, S.6
S.8 [4] S.462