Komplexitätstheorie II
Wintersemester 2005/2006
|
Vorlesung Komplexitätstheorie II |
|
|---|---|
SWS (V/Ü/P) | 2/0/0 |
Vorkenntnisse | Vordiplom, Komplexitätstheorie I |
Inhalt |
Es handelt sich im eine Fortsetzung der Vorlesung Komplexitätstheorie des letzten Wintersemesters. Es werden weitere interaktive Beweissysteme, eine Verallgemeinerung von nichtdeterministischen Algorithmen und ihre Anwendung auf Approximationsalgorithmen für NP-harte Probleme behandelt. Nach allgemeiner Einschätzung handelt es sich im eine der wichtigsten neueren Entwicklungen aus der Theoretischen Informatik. |
Literatur |
Ausiello, Crescenzi, Gambosi: Complexity and Approximation. |