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.

2023W, 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: 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.

 

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:0003.10.2023 - 19.12.2023Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu16:00 - 18:0005.10.2023EI 8 Pötzl HS - QUER entrance exam
Thu16:00 - 18:0012.10.2023EI 8 Pötzl HS - QUER entrance exam (alternate date)
Fri13:30 - 15:0024.11.2023Seminarraum FAV EG B (Seminarraum von Neumann) substitute date for January
Wed16:00 - 18:0029.11.2023Seminarraum 384 substitute date for January
Thu18:00 - 20:0011.01.2024Seminarraum FAV EG C (Seminarraum Gödel) Exam inspection and presentation of sample solutions
Wed16:00 - 18:0006.03.2024Seminarraum FAV EG B (Seminarraum von Neumann) Exam Inspection and presentation of sample solutions
Complexity theory - Single appointments
DayDateTimeLocationDescription
Tue03.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu05.10.202316:00 - 18:00EI 8 Pötzl HS - QUER entrance exam
Tue10.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu12.10.202316:00 - 18:00EI 8 Pötzl HS - QUER entrance exam (alternate date)
Tue17.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue24.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue31.10.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue07.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue14.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue21.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Fri24.11.202313:30 - 15:00Seminarraum FAV EG B (Seminarraum von Neumann) substitute date for January
Tue28.11.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Wed29.11.202316:00 - 18:00Seminarraum 384 substitute date for January
Tue05.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue12.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Tue19.12.202311:00 - 13:00Seminarraum FAV EG C (Seminarraum Gödel) lecture
Thu11.01.202418:00 - 20:00Seminarraum FAV EG C (Seminarraum Gödel) Exam inspection and presentation of sample solutions
Wed06.03.202416:00 - 18:00Seminarraum FAV EG B (Seminarraum von Neumann) Exam Inspection and presentation of sample solutions
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
Fri14:00 - 16:0001.03.2024 Inst. Logic and Compuation, Favoritenstrasse 9-11, Stairs 3, 3rd Floorwritten20.12.2023 00:00 - 28.02.2024 23:59TISSoral exam
Tue10:00 - 12:0005.03.2024Seminarraum FAV EG C (Seminarraum Gödel) written27.01.2024 00:00 - 03.03.2024 23:59TISSwritten exam

Course registration

Begin End Deregistration end
18.09.2023 00:00 05.10.2023 00:00 23.10.2023 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