Complexity theory traditionally considers decision problems, i.e., problems that have a yes/no answer. In many applications, however, one is not only interested in the existence of a solution, but also in actually obtaining the solutions. If a given problem has instances with exponentially many solutions, then an algorithm enumerating all solutions obviously needs exponential time in the worst case. However, the quality of such exponential enumeration algorithms may still vary considerably. For example, one can ask whether the algorithm has exponential runtime only if there are indeed exponentially many solutions, or how long the delay is between the generation of different solutions.
In the seminar, we will consider different such approaches for analyzing the complexity of enumeration algorithms and their application to enumeration problems in different areas of computer science.
List of papers
Hints on how to prepare a paper and how to give a talk are available (in German).