184.687 Seminar in 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.

2024S, SE, 2.0h, 3.0EC


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: SE Seminar
  • Format: Presence

Learning outcomes

After successful completion of the course, students are able to

  • to name advanced topics of complexity theory
  • to reproduce foundational research results on Problems beyond the classical complexity theory of decision problems
  • to overlook the relevant literature for counting and enumeration problems
  • to analyse the complexity of counting and enumeration problems

Subject of course

Usually, when detailed complexity analyses are carried out, we mean the complexity of decision problems. Here we have the most mature complexity theory at our disposal for the analysis and complexity classification of problems. However, in many applications, counting problems and enumeration problems are possibly yet more important than decision problems. For instance, in the database area, when evaluating queries, we are usually interested in the output of all answers rather than in the question, if at least one answer  exists.

Teaching methods

Students have to prepare oral presentations of selected research articles on topics treated in this seminar

Mode of examination


Additional information

ECTS Breakdown

 65 h Providing short sumaries and presentations
10 h Presence in class

 75 h = 3 Ects


It is planned to have the students' presentations "live" in the seminar room. If the Covid situation requires, these classes will switch to online via Zoom. The dates as announced in the first class are firm independently of the Covid situation.

Please consider the plagiarism guidelines of TU Wien when writing your seminar paper: Directive concerning the handling of plagiarism (PDF)



Course dates

Tue14:00 - 16:0012.03.2024Seminarraum FAV 01 A (Seminarraum 183/2) first class
Tue15:00 - 18:0030.04.2024 Room: meeting room of Institute 192, Favoritenstrasse, stairs 3, 3rd floorstudents' presentations on counting

Examination modalities

Assessement is based on the oral presentations

Course registration

Begin End Deregistration end
12.02.2024 00:00 11.03.2024 23:59 12.03.2024 23:59


Study CodeObligationSemesterPrecon.Info
066 931 Logic and Computation Mandatory elective


No lecture notes are available.

Previous knowledge

Prerequisite: VU Complexity Theory 181.142


if required in English