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

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

iCalendar

	Date and Time	Room and Remark
	Tue, 2019-04-23, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-04-23, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-04-24, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-04-26, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-04-26, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-04-29, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-04-30, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-04-30, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-03, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-03, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-05-06, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-05-07, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-05-07, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-05-08, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-05-10, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-10, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-05-13, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-05-14, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-05-14, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-05-15, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-05-17, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-17, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-05-20, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-05-21, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-05-22, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-05-24, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-24, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-05-27, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-05-28, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-05-28, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-05-29, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-05-31, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-05-31, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-06-03, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-06-04, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-06-04, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-06-05, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-06-07, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-06-07, 14:00–16:00	Boltzmannstr. 3
	Wed, 2019-06-12, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-06-14, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-06-14, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-06-17, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-06-18, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-06-18, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-06-19, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-06-21, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-06-21, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-06-24, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-06-25, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-06-25, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-06-26, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-06-28, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-06-28, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-07-01, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-07-02, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-07-02, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-07-03, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-07-05, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-07-05, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-07-08, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-07-09, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-07-09, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-07-10, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-07-12, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-07-12, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-07-15, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-07-16, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-07-16, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-07-17, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-07-19, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-07-19, 14:00–16:00	Boltzmannstr. 3
	Mon, 2019-07-22, 14:00–16:00	Boltzmannstr. 3
	Tue, 2019-07-23, 10:00–12:00	Boltzmannstr. 3
	Tue, 2019-07-23, 12:00–14:00	Boltzmannstr. 3
	Wed, 2019-07-24, 08:00–10:00	Boltzmannstr. 3
	Fri, 2019-07-26, 12:00–14:00	Boltzmannstr. 3
	Fri, 2019-07-26, 14:00–16:00	Boltzmannstr. 3

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

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)

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 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 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)