de | en

Complexity Theory (IN2007)

Course 0000002557 in SS 2019

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 Jan Kretinsky
Dates Fri, 14:00–16:00, MI 03.09.014
Fri, 12:00–14:00, MI 03.09.014
Tue, 12:00–14:00, MI 03.09.014
Tue, 10:00–12:00, MI 03.09.014
Wed, 08:00–10:00, MI 03.09.014
Mon, 14:00–16:00, MI 03.09.014

Assignment to Modules

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
TUMonline entry

Equivalent Courses (e. g. in other semesters)

SemesterTitleLecturersDates
SS 2021 Complexity Theory (IN2007) Ayikudi Ramachandrakumar, B. Ghoshdastidar, D. Mon, 10:00–12:00, virtuell
Tue, 14:00–16:00, virtuell
Thu, 16:00–18:00, virtuell
SS 2016 Complexity Theory (IN2007) Mon, 10:00–12:00, MI 03.09.014
Wed, 08:00–10:00, MI 02.13.010
Tue, 14:00–16:00, MI 02.13.010
SS 2015 Complexity Theory (IN2007) Mon, 14:00–16:00, MI 00.08.038
Thu, 14:00–16:00, MI 00.08.038
Tue, 12:00–14:00, MI 03.11.018
SS 2014 Complexity Theory (IN2007) Thu, 10:00–12:00, MI HS3
Thu, 12:00–14:00, MI 03.11.018
Mon, 08:00–10:00, MI 00.13.009A
SS 2013 Complexity Theory (IN2007)
Top of page