edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Daniel Rolf
Titel: Algorithms for the satisfiability problem
Gutachter: Martin Grohe; Stephan Kreutzer; Walter Kern
Erscheinungsdatum: 22.11.2006
Volltext: pdf (urn:nbn:de:kobv:11-10072180)
Fachgebiet(e): Informatik
Schlagwörter (ger): SAT, k-SAT, Erfüllbarkeit, Erfüllbarkeitsproblem, NP-hart, NP-vollständig
Schlagwörter (eng): SAT, k-SAT, satisfiability, satisfiability problem, NP-hard, NP-complete
Einrichtung: Humboldt-Universität zu Berlin
Zitationshinweis: Rolf, Daniel: Algorithms for the satisfiability problem; Dissertation, Humboldt-Universität zu Berlin , publiziert am 22.11.2006, urn:nbn:de:kobv:11-10072180
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Diese Arbeit befasst sich mit Worst-Case-Algorithmen für das Erfüllbarkeitsproblem boolescher Ausdrücke in konjunktiver Normalform. Im Wesentlichen betrachten wir Laufzeitschranken drei verschiedener Algorithmen, zwei für 3-SAT und einen für Unique-k-SAT. Wir entwickeln einen randomisierten Algorithmus, der eine Lösung eines erfüllbaren 3-KNF-Ausdrucks G mit n Variablen mit einer erwarteten Laufzeit von O(1.32793^n) findet. Der Algorithmus basiert auf der Analyse sogenannter Strings, welche Sequenzen von Klauseln der Länge drei sind. Dabei dürfen einerseits nicht aufeinanderfolgende Klauseln keine Variablen und andererseits aufeinanderfolgende Klauseln ein oder zwei Variablen gemeinsam haben. Gibt es wenige Strings, so treffen wir wahrscheinlich bereits während der String-Suche auf eine Lösung von G. 1999 entwarf Schöning einen Algorithmus mit einer Schranke von O(1.3334^n) für 3-SAT. Viele Strings erlauben es, die Laufzeit dieses Algorithmusses zu verbessern. Weiterhin werden wir den PPSZ-Algorithmus für Unique-k-SAT derandomisieren. Der 1998 von Paturi, Pudlak, Saks und Zane vorgestellte PPSZ-Algorithmus hat die besondere Eigenschaft, dass die Lösung eines eindeutig erfüllbaren 3-KNF-Ausdrucks in höchstens O(1.3071^n) erwarteter Laufzeit gefunden wird. Die derandomisierte Variante des Algorithmusses für Unique-k-SAT hat im Wesentlichen die gleiche Laufzeitschranke. Wir erreichen damit die momentan beste deterministische Worst-Case-Schranke für Unique-k-SAT. Zur Derandomisierung wenden wir die "Methode der kleinen Zufallsräume" an. Schließlich verbessern wir die Schranke für den Algorithmus von Iwama und Tamaki. 2003 kombinierten Iwama und Tamaki den PPSZ-Algorithmus mit Schönigs Algorithmus und konnten eine Schranke von O(1.3238^n) bewiesen. Um seinen Beitrag zum kombinierten Algorithmus zu steigern, justieren wir die Schranke des PPSZ-Algorithmusses. Damit erhalten wir die momentan beste randomisierte Worst-Case-Schranke für das 3-SAT-Problem von O(1.32216^n).
Abstract (eng):
This work deals with worst-case algorithms for the satisfiability problem regarding boolean formulas in conjunctive normal form. The main part of this work consists of the analysis of the running time of three different algorithms, two for 3-SAT and one for Unique-k-SAT. We establish a randomized algorithm that finds a satisfying assignment for a satisfiable 3-CNF formula G on n variables in O(1.32793^n) expected running time. The algorithm is based on the analysis of so-called strings, which are sequences of clauses of size three, whereby non-succeeding clauses do not share a variable, and succeeding clauses share one or two variables. If there are not many strings, it is likely that we already encounter a solution of G while searching for strings. In 1999, Schöning proved a bound of O(1.3334^n) for 3-SAT. If there are many strings, we use them to improve the running time of Schöning''s algorithm. Furthermore, we derandomize the PPSZ algorithm for Unique-k-SAT. The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the feature that the solution of a uniquely satisfiable 3-CNF formula can be found in expected running time at most O(1.3071^n). In general, we will obtain a derandomized version of the algorithm for Unique-k-SAT that has essentially the same bound as the randomized version. This settles the currently best known deterministic worst-case bound for the Unique-k-SAT problem. We apply the `Method of Small Sample Spaces'' in order to derandomize the algorithm. Finally, we improve the bound for the algorithm of Iwama and Tamaki to get the currently best known randomized worst-case bound for the 3-SAT problem of O(1.32216^n). In 2003 Iwama and Tamaki combined Schöning''s and the PPSZ algorithm to yield an O(1.3238^n) bound. We tweak the bound for the PPSZ algorithm to get a slightly better contribution to the combined algorithm.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 2 Zugriffe PDF: 4 Zugriffe Startseite: 2 Zugriffe PDF: 3 Zugriffe Startseite: 6 Zugriffe PDF: 3 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe Startseite: 2 Zugriffe PDF: 4 Zugriffe PDF: 1 Zugriffe Startseite: 2 Zugriffe PDF: 4 Zugriffe PDF: 13 Zugriffe PDF: 13 Zugriffe Startseite: 2 Zugriffe PDF: 2 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 1 Zugriffe PDF: 7 Zugriffe PDF: 3 Zugriffe PDF: 10 Zugriffe PDF: 7 Zugriffe PDF: 2 Zugriffe Startseite: 3 Zugriffe PDF: 23 Zugriffe PDF: 18 Zugriffe PDF: 15 Zugriffe Startseite: 2 Zugriffe PDF: 36 Zugriffe Startseite: 2 Zugriffe PDF: 30 Zugriffe Startseite: 2 Zugriffe PDF: 19 Zugriffe Startseite: 3 Zugriffe PDF: 15 Zugriffe Startseite: 5 Zugriffe PDF: 8 Zugriffe Startseite: 2 Zugriffe PDF: 15 Zugriffe Startseite: 5 Zugriffe PDF: 15 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 7 Zugriffe PDF: 17 Zugriffe Startseite: 4 Zugriffe PDF: 30 Zugriffe Startseite: 1 Zugriffe PDF: 27 Zugriffe Startseite: 4 Zugriffe PDF: 25 Zugriffe Startseite: 1 Zugriffe PDF: 25 Zugriffe Startseite: 1 Zugriffe PDF: 30 Zugriffe Startseite: 8 Zugriffe PDF: 51 Zugriffe Startseite: 4 Zugriffe PDF: 28 Zugriffe PDF: 26 Zugriffe Startseite: 6 Zugriffe PDF: 51 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Startseite 2 2 6 1 2   2     2 3 1         3     2 2 2 3 5 2 5 2 7 4 1 4 1 1 8 4   6
PDF 4 3 3 6 4 1 4 13 13 2 12 7 3 10 7 2 23 18 15 36 30 19 15 8 15 15 10 17 30 27 25 25 30 51 28 26 51

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 83 (2.24 pro Monat)
  • PDF – 608 (16.43 pro Monat)
 
 
Generiert am 26.10.2014, 06:29:37