"Komplexitaetstheorie 001.ps.gz" - читать интересную книгу автора

Universit"at Trier Fachbereich IV - Informatik

Christoph Meinel: Komplexit"atstheorie

Vorlesungsskript Sommersemester 2000

LATEX-Satz: Wolfgang Licht

Inhaltsverzeichnis 1 (Konzepte der) Komplexit"atstheorie 1

1.1 Probleme und Algorithmen : : : : : : : : : : : : : : : : : : : : : : : : : : : 1

1.1.1 Graph-Erreichbarkeitsproblem : : : : : : : : : : : : : : : : : : : : : 1 1.1.2 T RAV ELIN G SALESM AN - Problem (T SP ) : : : : : : : : : : : 4 1.2 Turingmaschinen (TM) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 1.3 Lineare Speed-Ups : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 1.4 Raumschranken und Platzsparen : : : : : : : : : : : : : : : : : : : : : : : 11 1.5 Nichtdeterministische Turingmaschinen : : : : : : : : : : : : : : : : : : : : 14 1.6 Komplexit"atsklassen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17

1.6.1 Komplement"are nichtdeterministische Komplexit"atsklassen : : : : : 19 1.7 Hierarchietheoreme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 1.8 Die Erreichbarkeitsmethode : : : : : : : : : : : : : : : : : : : : : : : : : : 24

1.8.1 Nichtdeterministischer Raum: Satz von Savitch (1970) : : : : : : : 26 1.8.2 Nichtdeterministischer Raum: Satz von Immerman / Szelepcz'enyi : 28

2 Die Klassen P und N P 31

2.1 Reduktion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 31 2.2 Vollst"andigkeit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 37

2.2.1 Die Berechnungstabellen-Methode : : : : : : : : : : : : : : : : : : : 38 2.3 Weitere Charakterisierung von N P : : : : : : : : : : : : : : : : : : : : : : 43 2.4 Weitere N P-vollst"andige Probleme : : : : : : : : : : : : : : : : : : : : : : 45

2.4.1 Varianten des Erf"ullbarkeitsproblems : : : : : : : : : : : : : : : : : 45 2.4.2 Graphtheoretische Probleme : : : : : : : : : : : : : : : : : : : : : : 50 2.4.3 Mengen- und Zahlentheoretische Probleme : : : : : : : : : : : : : : 58 2.5 N P und co N P : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68

i

INHALTSVERZEICHNIS ii

2.6 Randomisierte Berechnungen : : : : : : : : : : : : : : : : : : : : : : : : : : 72

2.6.1 Monte Carlo Algorithmen : : : : : : : : : : : : : : : : : : : : : : : 73 2.6.2 Random Walks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 2.6.3 Fermat Test : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 2.7 Randomisierte Komplexit"atsklassen : : : : : : : : : : : : : : : : : : : : : : 77 2.8 Die Polynomialzeithierarchie : : : : : : : : : : : : : : : : : : : : : : : : : : 81 2.9 L und N L : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 87

2.9.1 Das Problem L ?= N L : : : : : : : : : : : : : : : : : : : : : : : : : 88 2.9.2 Alternierende Komplexit"atsklassen : : : : : : : : : : : : : : : : : : 93 2.9.3 REACHABILIT Y f"ur ungerichtete Graphen : : : : : : : : : : : : 96 2.10 Z"ahlklassen oder die Bedeutung des Z"ahlens : : : : : : : : : : : : : : : : : 98

2.10.1 Die Permanente : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 98 2.11 Die Klasse \Phi P (Parity P) : : : : : : : : : : : : : : : : : : : : : : : : : : : 101