de | en

Complexity Theory (IN2007)

Course 821071343 in SS 2015

General Data

Course Type Lecture w/ Exercise
Semester Weekly Hours 6 SWS
Organisational Unit Informatics 14 - Chair of efficient algorithms (N.N.)
Dates 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

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)

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 2019 Complexity Theory (IN2007) Kretinsky, J. 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
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 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