Komplexitätstheorie

Vorlesung im SoSe 2011

Gehalten von Prof. Dr. Nicole Schweikardt
Betreuung der Übungen durch M.Sc. Frederik Harwath

Aktuelles

Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

• Am 30. Juni (Donnerstag) und 5. Juli (Dienstag) werden Vorlesung und Übung getauscht. D.h.: Am Donnerstag, den 30. Juni findet eine Vorlesung im Magnus-Hörsaal statt. Am Dienstag, den 5. Juli findet eine Übungsstunde statt.
• Die Übungen finden seit dem 28.04.2011 in Raum 117 in der Robert-Mayer-Straße 11-15 statt.
• Die erste Vorlesungsstunde fand in der ersten Semesterwoche am Dienstag, den 12.04.2011 von 14:15 Uhr bis 17:00 Uhr im Magnus-Hörsaal, Robert-Mayer-Str. 11-15, statt.
• Die erste Übungsstunde fand in der zweiten Semesterwoche am Donnerstag, den 21.04.2011 von 14:15 bis 16:00 Uhr im Magnus-Hörsaal, Robert-Mayer-Str. 11-15, statt.
• Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen finden Sie (nach den Vorlesungen) im Logbuch.
• In der letzten Übungsstunde vor Pfingsten (d.h. am 09.06.2011) und in der letzten Übungsstunde des Semesters (d.h. am 14.07.2011) wird ein 90-minütiger Test geschrieben, dessen Bestehen Teil der Voraussetzungen für den Scheinerwerb bzw. für das Einbringen von Bonuspunkten ist.

Einführung

Eine Beschränkung wichtiger Ressourcen wie Laufzeit und Speicherplatz auf realistische Dimensionen führt zu einer drastischen Einschränkung der Klasse lösbarer Probleme. Um dieses Phänomen zu studieren, wird, bei fixierten Ressourcen, die Komplexitätsklasse aller Probleme eingeführt, die innerhalb dieser Ressourcen lösbar sind. Wichtige Komplexitätsklassen wie Logspace, NC, P, NP und PSPACE werden eingeführt und ihre Eigenschaften werden untersucht. In der Veranstaltung wird sodann eine Auswahl der folgenden Themengebiete behandelt:

• ein Vergleich der Berechnungskraft deterministischer und randomisierter Berechnungen,
• der Entwurf von One-Way Funktionen und Pseudo-Random-Generatoren,
• eine Untersuchung der Parallelisierbarkeit von Algorithmen,
• eine Untersuchung der effizienten Approximierbarkeit von Problemen mit Hilfe des PCP-Theorems und
• Anwendungen der Kommunikationskomplexität und sonstiger Methoden in der Untersuchung von fundamentalen algorithmischen Problemen

Lernziele: Neben dem Verständnis der durch Ressourcenschranken bedingten Grenzen der algorithmischen Lösbarkeit ist die Fähigkeit, die Komplexität spezieller Probleme einzuschätzen und ein fundiertes Gefühl für das Machbare zu entwickeln, das wesentliche Ziel der Veranstaltung.

Kürzel laut Studienordnung: M-KTH.  Creditpoints: 8.  SWS: 3V, 2Ü.

Inhalte

Die Vorlesung wird voraussichtlich in folgende Kapitel gegliedert sein; die Inhalte orientieren sich jeweils an den entsprechenden Kapiteln des Buchs [AB] .

• Kapitel 0: Einleitung und grundlegende Notationen
• Kapitel 1: Das Berechnungsmodell - und warum Details der Definition nicht wichtig sind
• Kapitel 2: NP und NP-Vollständigkeit
• Kapitel 3: Diagonalisierung
• Kapitel 4: Platzkomplexität
• Kapitel 5: Die Polynomialzeit-Hierarchie und Alternierungen
• Kapitel 6: Boolesche Schaltkreise
• Kapitel 7: Randomisierte Berechnungen
• Kapitel 8: Der PCP-Satz

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

Termine

	Zeit	Ort	Leitung
Vorlesung	Dienstags 14:15-17:00 (Pausen: 15:00-15:05 und 15:50-16:05)	Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15	Prof. Dr. Nicole Schweikardt
Übung 1	Donnerstags 14:15-16:00	Raum 117, Robert-Mayer-Str. 11-15	M.Sc. Frederik Harwath

Übungsblätter

• Blatt 1 ( ausgeteilt am Di, 19.04.2011 ;  zu bearbeiten bis Do, 28.04.2011 )
• Blatt 2 ( ausgeteilt am Di, 26.04.2011 ;  zu bearbeiten bis Do, 05.05.2011 )
• Blatt 3 ( ausgeteilt am Di, 03.05.2011 ;  zu bearbeiten bis Do, 12.05.2011 )
• Blatt 4 ( ausgeteilt am Di, 10.05.2011 ;  zu bearbeiten bis Do, 19.05.2011 )
• Blatt 5 ( ausgeteilt am Di, 17.05.2011 ;  zu bearbeiten bis Do, 26.05.2011 )
• Blatt 6 ( ausgeteilt am Di, 24.05.2011 ;  zu bearbeiten bis Do, 02.06.2011 )
• Blatt 7 ( ausgeteilt am Di, 31.05.2011 ;  zu bearbeiten bis Do, 09.06.2011 )
• Blatt 8 ( ausgeteilt am Di, 07.06.2011 ;  zu bearbeiten bis Do, 16.06.2011 )
• Blatt 9 ( ausgeteilt am Di, 21.06.2011 ;  zu bearbeiten bis Do, 30.06.2011 )
• Blatt 10 ( ausgeteilt am Di, 05.07.2011 ;  zu bearbeiten bis Do, 14.07.2011 )

Prüfungen bzw. Scheine

Vorsicht:

In der Vorlesung und der Übung werden viele wichtige Dinge (insbesondere Beweise, aber auch einiges andere) an der Tafel erklärt. Diese Dinge sind für die Veranstaltung "Komplexitätstheorie" wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den hier erhältlichen pdf-Dateien enthalten sind.
Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung oder Diplom-Prüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungsstunden (mit Folien oder an der Tafel) vermittelte Material durchzuarbeiten.

Modulabschlussprüfung (relevant für Studierende in einem Bachelor- oder Master-Studiengang):

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt.
Termine für mündliche Modulabschlussprüfungen können nach Vereinbarung bei Frau Nadland angefragt werden. Generelle Informationen zur Anmeldung zu mündlichen Prüfungen finden hier.

Im Lauf des Semesters können Bonuspunkte erworben werden, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann (also von 4,0 auf 3,7; von 3,7 auf 3,3; von 3,3 auf 3,0; von 3.0 auf 2,7; von 2,7 auf 2,3; von 2,3 auf 2,0; von 2,0 auf 1,7; von 1,7 auf 1,3; von 1,3 auf 1,0).

In der letzten Übungsstunde vor Pfingsten (d.h. am 09.06.2011) und in der letzten Übungsstunde des Semesters (d.h. am 14.07.2011) wird je ein 90-minütiger Test geschrieben.
Voraussetzung für den Erwerb von Bonuspunkten, durch deren Einbringen die Note einer bestandenen Modulabschlussprüfung um eine Teilnote verbessert werden kann, sind:

1. Bestehen der beiden Tests und
2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Scheinerwerb (relevant für Studierende in einem Diplom- oder Lehramts-Studiengang):

In der letzten Übungsstunde vor Pfingsten (d.h. am 09.06.2011) und in der letzten Übungsstunde des Semesters (d.h. am 14.07.2011) wird je ein 90-minütiger Test geschrieben.
Voraussetzung für den Scheinerwerb sind:

1. Bestehen der beiden Tests und
2. Erreichen von mindestens 50 Prozent aller Übungspunkte (bitte beachten Sie, dass dies insbes. die regelmäßige und aktive Teilnahme an den Übungsstunden erfordert, siehe unten).

Verbindliche "Spielregeln" zum Erwerb von Übungspunkten:

Übungsblätter werden dienstags nach der Vorlesung ausgeteilt. Am Donnerstag der darauf folgenden Woche wird das jeweilige Übungsblatt in der Übungsstunde besprochen. Zu Beginn dieser Übungsstunde können alle Teilnehmer in eine Liste eintragen, für welche Aufgaben(teile) sie wie viele Übungspunkte angerechnet bekommen wollen. Während der Übungsstunde werden vom Übungsleiter aus dieser Liste willkürlich einzelne Teilnehmer zum Vorrechnen von Aufgaben(teilen) ausgesucht. Falls sich beim Vorrechnen herausstellen sollte, dass ein Teilnehmer keine sinnvolle Lösung vorweisen kann, obwohl er in der Liste Übungspunkte für diese Aufgabe beansprucht hat, geschieht folgendes:

1. Tritt diese Situation für den jeweiligen Teilnehmer zum ersten Mal in diesem Semester auf, so werden ihm für das gesamte gerade behandelte Übungsblatt keine Übungspunkte angerechnet.
2. Tritt diese Situation für den jeweiligen Teilnehmer zum zweiten Mal in diesem Semester auf, so kann er in der Veranstaltung "Komplexitätstheorie" im SoSe 2011 keine Übungspunkte erwerben.

Literatur

[AB]	Sanjeev Arora and Boaz Barak. Computational Complexity. A Modern Approach. Cambridge University Press, 2009.
[G]	Oded Goldreich. Computational Complexity. A Conceptual Perspective. Cambridge University Press, 2008.
[P]	Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1995.
[W]	Ingo Wegener. Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer-Verlag, 2003.
[AB]	Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
[HU]	J. E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[S]	Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
[K]	Dexter Kozen. Theory of Computation. Springer-Verlag, 2006.
[V]	Heribert Vollmer. Introduction to Circuit Complexity. Springer-Verlag, 1999.

Links

[LF-Blog]	Lance Fortnow's Computational Complexity Blog
[RJL-Blog]	Richard J. Lipton's Theory of Computation Blog
[CCC]	IEEE Conference on Computational Complexity (CCC)