Complexity Theory (IN2007)
Course 0000002557 in SS 2021
General Data
Course Type | lecture with integrated exercises |
---|---|
Semester Weekly Hours | 6 SWS |
Organisational Unit | Informatics 7 - Chair of Theoretical Computer Science (Prof. Esparza) |
Lecturers |
Balasubramanian Ayikudi Ramachandrakumar Debarghya Ghoshdastidar |
Dates |
Mon, 10:00–12:00, virtuell Tue, 14:00–16:00, virtuell Thu, 16:00–18:00, virtuell |
Assignment to Modules
-
IN2007: Komplexitätstheorie / Complexity Theory
This module is included in the following catalogs:- Catalogue of non-physics elective courses
Further Information
Courses are together with exams the building blocks for modules. Please keep in mind that information on the contents, learning outcomes and, especially examination conditions are given on the module level only – see section "Assignment to Modules" above.
additional remarks | Turing Machine model. Time and space complexity. Circuits as computational model. L, NL, P, NP, PSPACE, EXP, NEXP, PH. Co-classes. Completeness and fundamental structural relationships between complexity classes. Optional topics: Structural complexity theory. Lower Bounds. Descriptive complexity theory. Functional problems, optimization problems and their approximization (PCP-Theorem), complexity for cryptography. |
---|---|
Links |
Course documents E-Learning course (e. g. Moodle) TUMonline entry |
Equivalent Courses (e. g. in other semesters)
Semester | Title | Lecturers | Dates |
---|---|---|---|
WS 2023/4 | Complexity Theory (IN2007) | Ghoshdastidar, D. Guttenberg, R. |
Tue, 10:00–12:00, MI 03.09.014 Wed, 14:00–16:00, MI 03.09.014 Thu, 10:00–12:00, MI 03.09.014 |
SS 2019 | Complexity Theory (IN2007) | Kretinsky, J. |
Tue, 10:00–12:00, MI 03.09.014 Tue, 12:00–14:00, MI 03.09.014 Wed, 08:00–10:00, MI 03.09.014 Fri, 12:00–14:00, MI 03.09.014 Fri, 14:00–16:00, MI 03.09.014 Mon, 14:00–16:00, MI 03.09.014 |
SS 2016 | Complexity Theory (IN2007) |
Mon, 10:00–12:00, MI 03.09.014 Tue, 14:00–16:00, MI 02.13.010 Wed, 08:00–10:00, MI 02.13.010 |
|
SS 2015 | Complexity Theory (IN2007) |
Mon, 14:00–16:00, MI 00.08.038 Tue, 12:00–14:00, MI 03.11.018 Thu, 14:00–16:00, MI 00.08.038 |
|
SS 2014 | Complexity Theory (IN2007) |
Mon, 08:00–10:00, MI 00.13.009A Thu, 10:00–12:00, MI HS3 Thu, 12:00–14:00, MI 03.11.018 |
|
SS 2013 | Complexity Theory (IN2007) |