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