Complexity Theory
Aus International Center for Computational Logic
Complexity Theory
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2015
Dozent
- Daniel Borchmann, Markus Krötzsch
Tutor
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Mündliche Prüfung
This course covers the fundamental concepts as well as advanced topics of complexity theory.
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | Introduction | DS4, 14. Oktober 2015 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Turing Machines and Languages | DS4, 16. Oktober 2015 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Undecidability | DS2, 20. Oktober 2015 in APB E005 | |
| Vorlesung | Undecidability | DS4, 21. Oktober 2015 in APB E005 | |
| Übung | Mathematical Foundations | DS4, 23. Oktober 2015 in APB E005 | |
| Vorlesung | Rice's Theorem for Recognizability | DS2, 27. Oktober 2015 in APB E005 | |
| Vorlesung | A Hierarchy of Undecidable Problems | DS4, 28. Oktober 2015 in APB E005 | |
| Übung | Turing Machines and Languages | DS4, 30. Oktober 2015 in APB E005 | |
| Vorlesung | The Recursion theorem | DS2, 3. November 2015 in APB E005 | |
| Vorlesung | Decidability and Logic | DS4, 4. November 2015 in APB E005 | |
| Übung | Undecidability and Rice's Theorem | DS4, 6. November 2015 in APB E005 | |
| Vorlesung | Time Complexity: Polynomial Time | DS2, 10. November 2015 in APB E005 | Datei |
| Vorlesung | Time Complexity: NP | DS4, 11. November 2015 in APB E005 | Datei |
| Übung | The Recursion Theorem and Decidability in Logic | DS4, 13. November 2015 in APB E005 | |
| Vorlesung | Time Complexity: NP Completeness | DS2, 17. November 2015 in APB E005 | Datei 1, Datei 2 |
| Übung | Time Complexity | DS4, 20. November 2015 in APB E005 | |
| Vorlesung | NP-Complete Problems | DS2, 24. November 2015 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Space Complexity | DS4, 25. November 2015 in APB E005 | Datei 1, Datei 2 |
| Übung | Time Complexity | DS4, 27. November 2015 in APB E005 | |
| Vorlesung | Polynomial Space | DS2, 1. Dezember 2015 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Games/Logarithmic Space | DS4, 2. Dezember 2015 in APB E005 | Datei 1, Datei 2 |
| Übung | Space Complexity | DS4, 4. Dezember 2015 in APB E005 | |
| Vorlesung | The Time Hierarchy Theorem | DS2, 8. Dezember 2015 in APB E005 | |
| Vorlesung | More on Hierarchy Theorems, the Gap Theorem | DS4, 9. Dezember 2015 in APB E005 | |
| Übung | Space Complexity | DS4, 11. Dezember 2015 in APB E005 | |
| Vorlesung | Ladner's Theorem | DS2, 15. Dezember 2015 in APB E005 | |
| Vorlesung | The Baker-Gill-Solovay Theorem | DS4, 16. Dezember 2015 in APB E005 | |
| Übung | Mid-Term Consultation | DS4, 18. Dezember 2015 in APB E005 | |
| Vorlesung | Alternating Turing Machines | DS2, 5. Januar 2016 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Alternating Complexity Classes | DS4, 6. Januar 2016 in APB E005 | Datei 1, Datei 2 |
| Übung | Diagonalization | DS4, 8. Januar 2016 in APB E005 | |
| Vorlesung | The Polynomial Hierarchy | DS2, 12. Januar 2016 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Circuit Complexity | DS4, 13. Januar 2016 in APB E005 | Datei 1, Datei 2 |
| Übung | Alternation | DS4, 15. Januar 2016 in APB E005 | |
| Vorlesung | Circuits for Parallel Computation | DS2, 19. Januar 2016 in APB E005 | Datei 1, Datei 2 |
| Vorlesung | Randomized Computation | DS4, 20. Januar 2016 in APB E005 | |
| Übung | Circuit Complexity | DS4, 22. Januar 2016 in APB E005 | |
| Vorlesung | Randomized Computation | DS2, 26. Januar 2016 in APB E005 | |
| Vorlesung | Randomized Computation | DS4, 27. Januar 2016 in APB E005 | |
| Übung | Randomized Computation | DS4, 29. Januar 2016 in APB E005 | |
| Vorlesung | Randomized Computation | DS2, 2. Februar 2016 in APB E005 | |
| Vorlesung | Wrapup and Outlook | DS4, 3. Februar 2016 in APB E005 | |
| Übung | Consultation | DS4, 5. Februar 2016 in APB E005 |
Kalender
