181.142 Complexity theory
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021W, VU, 2.0h, 3.0EC, to be held in blocked form
TUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to

  • explain fundamental complexity classes and their intuition
  • carry out complexity analyses of problems (in particular in the Polynomial Hierarchie)

Subject of course

Basic notions of complexity theory, deterministic und non-deterministic complextiy classes, NP-complete problems, logarithmic space, the polynomal hierarchy, exponentially hard probleme, applications.

Teaching methods

The material is presented by the lecturer. The students have to solve exercises.

Mode of examination

Written and oral

Additional information

ECTS Breakdown

  2 h quiz 
30 h lecture (12 classes including preparation)
40 h exam preparation
3 h written + oral exam
-----------------------------------------------------------
75 h = 3 Ects

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri11:00 - 13:0001.10.2021 - 28.01.2022 online via Zoom: see TUWEL for the zoom link (LIVE)lecture
Complexity theory - Single appointments
DayDateTimeLocationDescription
Fri01.10.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri08.10.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri15.10.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri22.10.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri29.10.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri05.11.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri12.11.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri19.11.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri26.11.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri03.12.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri10.12.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri17.12.202111:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri14.01.202211:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri21.01.202211:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Fri28.01.202211:00 - 13:00 online via Zoom: see TUWEL for the zoom linklecture
Course is held blocked

Examination modalities

Assessment consists of 3 components:

  • entrance test
  • exercises
  • written and/or oral exam at the end (details to be announced in the first class)

 

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Thu16:00 - 18:0019.01.2023EI 8 Pötzl HS - QUER written01.12.2022 00:00 - 18.01.2023 00:00TISSwritten exam

Course registration

Begin End Deregistration end
13.09.2021 00:00 01.10.2021 00:00 18.10.2021 00:00

Curricula

Literature

C. Papadimitriou. "Computational Complexity". Addison-Wesley, 1994. M. R. Garey and D. S. Johnson. "Computers and Intractability". Freeman, 1979.

Previous knowledge

  • Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory (to the extent taught in the course "Formale Methoden der Informatik").
  • Moreover, students should have basic mathematical skills (like carrying out proofs by induction) as taught in the mathematics courses in the bachelor studies.

Miscellaneous

Language

English