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.

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

Course evaluation

Properties

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

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 (including exercises) is presented by the lecturer.

Remark: The course in the WS 2022 is planned to be held in person. If required by the Covid situation, the course will be held online via Zoom. All dates and times (classes as well as written exam) remain the same in this case.

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
Tue11:00 - 13:0004.10.2022 - 24.01.2023Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu16:00 - 18:0006.10.2022EI 8 Pötzl HS - QUER entrance test
Thu16:00 - 18:0013.10.2022EI 8 Pötzl HS - QUER entrance test, alternative date
Complexity theory - Single appointments
DayDateTimeLocationDescription
Tue04.10.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu06.10.202216:00 - 18:00EI 8 Pötzl HS - QUER entrance test
Tue11.10.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu13.10.202216:00 - 18:00EI 8 Pötzl HS - QUER entrance test, alternative date
Tue18.10.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue25.10.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue08.11.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue22.11.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue29.11.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue06.12.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue13.12.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue20.12.202211:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue10.01.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue17.01.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue24.01.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
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
Fri - 03.02.2023written17.01.2023 00:00 - 01.02.2023 23:59TISSoral exam
Wed - 22.02.2023oral17.01.2023 00:00 - 20.02.2023 23:59TISSoral exam

Course registration

Begin End Deregistration end
19.09.2022 00:00 07.10.2022 00:00 24.10.2022 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