Komplexitätstheorie II

Prof. Peter Bürgisser, Sommersemester 2009


Termine

Vorlesung (V2)
Mo 09:00 - 10:30       D1.320  Peter Bürgisser

Übung (Ü1)
zweiwöchig
Mo 07:30 - 09:00       D1.320  Christian Ikenmeyer
Beginn Vorlesung
Mo 20. April
Termine Übung
Mo 11. Mai, 25. Mai, 8. Juni, 22. Juni, 6. Juli

Aktuelles

Übungsblätter

Die Übungsaufgaben sind jeweils bis zum Donnerstag vor der Übungsgruppe 11:00 Uhr in den Kasten neben dem Raum D3.328 einzuwerfen.


Inhalt der Vorlesung

In dieser Vorlesung sollen ausgewählte Themen der Komplexitätstheorie behandelt werden. Die Vorlesung richtet sich insbesondere an Studierende für den Masterstudiengang Informatik.

Die Komplexitätstheorie ist eine wichtige Ergänzung der Theorie der Algorithmen. Ihr Ziel ist es zu verstehen, warum gewisse Berechnungsprobleme schwierig sind und diese anhand ihrer Schwierigkeit zu klassifizieren.

Der Fokus der Vorlesung ist auf arithmetischen Berechnungsmodellen und Valiants arithmetischer Theorie der NP-Vollständigkeit (VP versus VNP). Weitere Themen sind die verwandte Theorie der #P-Vollständigkeit und Todas Theorem. Eventuell besprechen wir auch die bemerkenswerten unteren Schranken von Ran Raz im multilinearen Berechnungsmodell.

Inhalt

Inhaltsangabe: [ pdf ]

Formales

Studienbegleitende Modulprüfung (oder Scheinkriterium)
Kriterium für einen Schein sind 50 % der Übungspunkte. Eine benotete mündliche Prüfung wird nach Absprache angeboten.
Hörerkreis
i6, ma6, Modelle und Algorithmen
Vorkenntnisse
Komplexitätstheorie I (im Bachelorstudiengang)

Literaturangaben