This site is available only in German.

Komplexitätstheorie – SoSe19

Im Logbuch finden Sie Informationen zum Inhalt der einzelnen Vorlesungsstunden.

Aktuelles

Inhalt der Veranstaltung

In der Komplexitätstheorie versuchen wir zu verstehen, welche Eigenschaften ein algorithmisches Problem schwierig machen. Beispielsweise haben wir bereits in der Theoretischen Informatik 1 die Klasse der NP-harten Probleme kennengelernt, zu deren deterministischer Lösung ein polynomieller Aufwand der Ressource "Laufzeit" vermutlich nicht ausreichend ist.

Wir betrachten Probleme, wie etwa die Berechnung von Gewinnstrategien für Zwei-Personen-Spiele oder die Frage, ob zwei NFAs äquivalent sind: Diese Probleme werden wahrscheinlich noch nicht einmal in der Klasse NP liegen, wir führen deshalb die Klasse PSPACE aller in polynomiellem Speicherplatz lösbaren Probleme ein. Desweiteren stellen wir einen allgemeinen Zusammenhang zwischen Parallelisierbarkeit und Speicherplatzkomplexität her.

Angenommen, ein Außerirdischer besucht die Erde und versucht, uns eine Gewinnstrategie für das Schachspiel zu verkaufen. Natürlich vertrauen wir dem Außerirdischen nicht. Können wir uns davon überzeugen, dass es sich tatsächlich um eine Gewinnstrategie handelt (obwohl unsere Intelligenz der Intelligenz des Außerirdischen um ein Vielfaches unterlegen ist)? Mit interaktiven Beweissystemen kann diese Frage bejaht werden. Die Frage nach der Approximationskomplexität erfordert eine gänzlich neue Sichtweise auf die Klasse NP, und zwar die Sichtweise von probabilistisch überprüfbaren Beweisen und damit kommen wir wieder zu interaktiven Beweissystemen zurück.

Im letzten Teil behandeln wir Quantenalgorithmen. Wir zeigen, dass die unstrukturierte Suche quadratisch beschleunigt werden kann und brechen klassische kryptographische Verfahren wie das RSA-Public-Key-Kryptosystem. Mit Methoden der Gitterkryptographie scheint man andererseits Quantenangriffen erfolgreich widerstehen zu können.
Warum kann man bisher nicht zeigen, dass P eine echte Teilklasse von NP ist? Wir benutzen kryptographische Methoden, um zu zeigen, dass vermutlich radikal neue Beweismethoden notwendig sind.

Veranstaltungsform

Vorlesung + Übung (SWS: 4+2)

Literaturhinweise

  • S. Aaronson, Quantum Computing since Democritus, Cambridge University Press, 2013.
  • S. Arora und B. Barak, Computational Complexity, a Modern Approach, Cambridge University Press, 2009.
  • M. Sipser, Introduction to the Theory of Computation, Paperback 3rd edition, Cengage Learning, 2012.

Blogs

Termine

Vorlesung:
  • Montag, 12 (c.t.) bis 14 Uhr im Magnus-Hörsaal
  • Dienstag, 8:30 bis 10:00 Uhr im Magnus-Hörsaal
Übung:
  • Mittwoch, 8:30 bis 10:00 Uhr in SR 11

Material

Kontakt

Bei Fragen helfen Hannes Seiwert und Mario Holldack gerne weiter.

Übungsbetrieb

Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen. Die Abgabe bearbeiteter Blätter erfolgt

  • montags
  • vor Vorlesungsbeginn
  • im Hörsaal.

Falls ein Erscheinen nicht einzurichten ist, ist eine frühere Abgabe im großen Briefkasten zwischen Raum 312 und 313 (RMS 11-15) ebenfalls zulässig. Dieser Briefkasten wird am Abgabetag vor Vorlesungsbeginn geleert. Später eingeworfene Abgaben werden nicht gewertet.

Damit ein reibungsloser Ablauf gewährleistet werden kann, muss jede Abgabe im Kopf der Titelseite gut leserlich mit Name und Matrikelnummer versehen sein.

Abgaben, die mehrere Blätter umfassen, müssen mittels eines Tackers zusammengefügt sein. An der Ecke zusammengefaltete Blätter, Büroklammern o.ä. ersetzen keine Tackernadel! Für nicht getackerte Abgaben kann nicht gewährleistet werden, dass sie vollständig korrigiert werden.

Übungsgruppen

Beginnend mit der zweiten Vorlesungswoche erscheinen wöchentlich Übungsblätter. Das erste Übungsblatt erscheint am Dienstag, dem 23. April. Die Übungsgruppe trifft sich das erste Mal ausnahmsweise am Dienstag, dem 30. April zur Besprechung des ersten Übungsblattes. In den folgenden Wochen findet das Tutorium mittwochs statt.

Prüfung

Studiengänge

Für den Master Informatik (PO 2015) gliedert sich die Veranstaltung auf in
  • Komplexitätstheorie 1 (5 CP, die Veranstaltung findet vom 15.04. bis zum 31.05. statt) und
  • Komplexitätstheorie 2 (5 CP, die Veranstaltung findet vom 03.06. bis zum 19.07. statt).
Für den alten Master Informatik (PO 2007) und den Master Wirtschaftsinformatik können nur beide Veranstaltungen zusammen geprüft werden (im Umfang von 10 CP).

Mündliche Prüfungen/Klausur

Abhängig von der Teilnehmerzahl finden mündliche Prüfungen oder eine Klausur nach Vorlesungsende statt. Mündliche Prüfungen werden nach Vereinbarung abgehalten. Übungspunkte werden bonifiziert: bei Erreichen von 50 % bzw. 70 % der möglichen Übungspunkte kann die Prüfungsnote um einen bzw. zwei Notenschritte verbessert werden, falls die Prüfung bestanden ist.