de | en

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

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)

SemesterTitleLecturersDates
SS 2019 Complexity Theory (IN2007) Kretinsky, J. Fri, 14:00–16:00, MI 03.09.014
Mon, 14:00–16:00, MI 03.09.014
Wed, 08:00–10:00, MI 03.09.014
Tue, 12:00–14:00, MI 03.09.014
Tue, 10:00–12:00, MI 03.09.014
Fri, 12:00–14: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
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