A faster approximation scheme for #k-SAT
Exploiting independent subformulars
©2014
Hausarbeit (Hauptseminar)
15 Seiten
Zusammenfassung
Diese Ausarbeitung zum Thema „Approximationsschema für #k-SAT“ entstand im Rahmen des Seminars „Algorithmische Schönheiten“ im Wintersemester 2013/14. Zunächst werden relevante Grundlagen vorgestellt. Danach wird der Algorithmus von Thurley beleuchtet. Dieser ist der Ausgangspunkt für die anschließend vorgestellten Verbesserungen. Sofern nichts anderes erwähnt wird, beziehen sich die Inhalte dieser Arbeit auf das Paper [SCH13].
Leseprobe
Inhaltsverzeichnis
1
Inhaltsverzeichnis:
1. Vorwort
3
2. Grundlagen
3
3. Elimination trees
7
4. Der -cut
8
5. Monte Carlo Simulation
9
6. Thurley´s RAS
10
7. Pruning the tree
11
8. Unabhängige Formeln
13
Literaturverzeichnis
15
2
1. Vorwort
Diese Ausarbeitung zum Thema ,,Approximationsschema für # -SAT" entstand im
Rahmen des Seminars ,,Algorithmische Schönheiten" im Wintersemester 2013/14.
Zunächst werden relevante Grundlagen vorgestellt. Danach wird der Algorithmus von
Thurley beleuchtet. Dieser ist der Ausgangspunkt für die anschließend vorgestellten
Verbesserungen. Sofern nichts anderes erwähnt wird, beziehen sich die Inhalte dieser
Arbeit auf das Paper [SCH13].
2. Grundlagen
In diesem Kapitel sollen die notwendigen Grundlagen für die nachfolgende Ausarbeitung
dargestellt werden.
Definition 1: Sei = { , ... ,
} die Menge der Variablen. Ein Literal ist eine Variable
( {1, ... , }) oder ihre Negation ( {1, ... , }).
Eine Klausel
=
...
ist eine oder-Verknüpfung von Literalen. Eine Boolsche ( , ) -Formel
=
...
in konjunktiver Normalform (KNF) ist eine und-Verknüpfung von Klauseln über
Variablen aus .
Beispiel 2: Sei = { , }. Dann ist =
(
) eine (2,2) -Formel in KNF.
Definition 3: Eine Probleminstanz heißt eine -KNF, wenn jede Klausel höchstens
Länge hat. Das Problem -SAT bezeichnet Boolsche Formeln, in der alle Klauseln aus
höchstens Literalen bestehen.
3
Beispiel 4:
Sei = { , , , }. Die Boolsche (4,4) -Formel
= (
) (
) (
)
ist eine Probleminstanz von 2 -SAT, denn jede Klausel in dieser Formel besteht aus
höchstens 2 Literalen.
Gibt es eine Zuweisung boolscher Werte : {0,1} zu den Variablen, so dass
( ) = TRUE,
so ist die boolsche Formel erfüllbar. Andernfalls gibt es keine Belegung, welche die
boolsche Formel erfüllt.
Satz 5: 2 -SAT liegt in P. -SAT ist NP-vollständig für 3.
Die nachfolgende Tabelle soll eine Übersicht über die Laufzeiten der schnellsten
Algorithmen für -SAT geben.
Deterministische
Algorithmen
Randomisierte
Algorithmen
= 2
( + )
-
= 3
(1,3303 )
(log (
) 1,30704 )
= 4
(1,5 )
(log (
) 1,46899 )
Abbildung 1: Schnellste Algorithmen für -SAT
Die Bedeutung von ist im Fall randomisierter Algorithmen:
Falls die boolsche Formel nicht erfüllbar ist, gibt der Algorithmus die richtige Antwort
aus. Sonst gibt er mit Wahrscheinlichkeit 1 - eine erfüllende Belegung aus.
Häufig will man nicht nur eine Lösung bestimmen, sondern die Anzahl der
verschiedenen Lösungen bestimmen. Die hierzu gehörende Komplexitätsklasse ist #P.
Um die Komplexität des Zählproblems einordnen zu können, wird im Folgenden die
Komplexitätsklasse #P vorgestellt.
4
Definition 6: Eine zählende Turing-Maschine ist eine nichtdeterministische Turing-
Maschine, welche die Anzahl der akzeptierenden Berechnungen zu einer Eingabe auf
einem zusätzlichen Band ausgibt. Sie hat die Zeit-Komplexität f(n), falls die längste
akzeptierende Berechnung zu einer Eingabe von Größe n f(n) Schritte benötigt (aus
[SEN 14]).
Definition 7: #P ist die Menge aller Probleme, die von zählenden Turing-Maschinen mit
polynomieller Zeit-Komplexität berechnet werden können (aus [SEN 14]).
Definition 8: Ein Problem A ist #P-vollständig, genau dann wenn gilt:
#
# :
#SAT ist das Problem die Anzahl der erfüllenden Belegungen zu bestimmen. # -SAT ist
das Problem die Anzahl der erfüllenden Belegungen einer -KNF zu bestimmen. Für
2 ist #SAT und # -SAT #P-vollständig. Die nachfolgende Tabelle soll die besten
Laufzeiten für # -SAT darstellen.
exakt
randomisiert
Paper
= 2
1,2377
-
-
= 3
1,6423
1,5366
1,51426
= 4
1,9275
1,6155
1,60816
Abbildung 2: Laufzeiten für # -SAT
Definition 9: Sei = # und der größte zulässige Fehler. Der Input sei . Ein
randomisiertes Approximationsschemata gibt eine Zufallsvariable A aus, die mit
hoher Wahrscheinlichkeit der gesuchten Größe nahe kommt:
(1 - )
(1 + )
1 -
heißt dann auch -Approximation von # .
5
und sollen möglichst klein sein. Effizient sind solche Algorithmen wenn ihre Laufzeit
polynomial beschränkt ist in ,
und
. Dabei ist die Rolle von nebensächlich,
denn ist die Wahrscheinlichkeit strikt größer als , so lässt sie sich durch eine Erhöhung
der Laufzeit um lediglich (log (
) anhand der median of means method auf 1-
vergrößern (vgl. [FEH 03]).
6
3. Elimination trees
Gesucht ist ein Entscheidungsbaum für eine -KNF mit Levels {0, ... , }. Fixiere hierzu
eine Eliminationsreihenfolge ( , ... , ) der Variablen. Jeder Knoten des Baumes
entspricht einer boolschen Formel. Die Wurzel (Level 0) des Baumes ist gerade . Jeder
Knoten jedes Levels i (0 i < n) hat die beiden Nachfolger
und
. Deshalb
entspricht ein Weg von der Wurzel zu einem Blatt des Baumes einer Zuordnung von
Werten zu den Variablen. Am Blatt ist der Wert schließlich 1 oder 0.
# ist dann die Anzahl der Blätter mit Wert 1.
Abbildung 3: Beispiel eines Elimination trees
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2014
- ISBN (eBook)
- 9783956363757
- Dateigröße
- 2.6 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Fachhochschule für Verwaltung Saarland; Saarbrücken – Informatik
- Erscheinungsdatum
- 2014 (Oktober)
- Note
- unbenotet
- Schlagworte
- exploiting
