Building on the Complexity Theory course, we will touch on more advanced topics in the area of complexity theory. In the winter term 2016/7, we will have a closer look at the complexity of "counting problems" and "enumeration problems".
The participants of the seminar will get acquainted with essential research articles on "counting problems" and "enumeration problems". We will thus look at both, classical foundational articles in these areas and articles from the more recent research literature with complexity analyses of concrete (counting and enumeration) problems.
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.
65 h Providing short sumaries and presentations 10 h Presence in class ----------------------------------------------------------------
75 h = 3 Ects
In the course of the semester, each participant will work on 2 research articles, i.e.: providing a short summary and presentation in class. Further details will be provided in the first class.
Prerequisite: VU Complexity Theory 181.142
