(Je nach Wunsch/Bedarf der Studierenden wird das Seminar auf Deutsch oder Englisch durchgeführt.
Depending on the wishes/demands of the students, this seminar can be held in English or German.)

Based on a classical research paper, the participants will give oral presentations and write short summaries about algorithmic problems and their complexity. Algorithmic solutions will be discussed and, as a practical exercise, implemented in a proof-of-concept fashion. Talks and essays can be done in German or English. The first day covers an introduction into the topic and an overview of possible topics, which will then be distributed to the students. Aspects of scientific writing and presenting will be covered as well.

The overarching topic of this semester are “Karp's 21 NP-complete problems”: Richard M. Karp. "Reducibility among combinatorial problems" (1972) In this work, Karp shows NP-hardness of many classical, important formal problems, mainly by listing reductions/equivalence between them. The given reductions appear like brief cooking recipes, but no intuition or proof of equivalence is provided. The relations are not too obvious but also not too hard to see – excellent exercises for understanding formal statements, logical thinking, formal writing etc.

Each participant will be responsible for one reduction, understand it and explain it to the others. We will pre-select a list of appropriate problems and provide help where necessary.

Concrete tasks are:

• Understand the reduction