## Schedule

**Final report:**Submit a short paper (“Ausarbeitung”) on your topic (~5 pages) by**October 21**.**Seminar dates:**August 18 and October 4 from 9:15 to 14:00 (Campus E1.1, Room 206).- Until end of semester: Prepare for your talk! If you have any questions or need guidance, just drop by our offices (Campus E1.3, Room 426 and 414)
- Second meeting: May 23 at 14 c.t. in Room 107 of E1 3.
- Attempt the following exercises: Assignment 1

- First meeting: April 24 at 14 c.t. in Room 107 of E1 3.

## Description

The P versus NP Problem is one of the most important problems in computer science and mathematics. It has been selected as one of seven Millennium Prize Problems; whoever can resolve the problem by providing a mathematical proof that P≠NP or P=NP holds will be awarded $1 million.

### What does it mean?

Apart from the mathematical formulation of the question, we may discuss social, economic, and philosophic implications of the P versus NP problem. For example, it may turn out that every cryptographic scheme can, in principle, be broken! Impagliazzo lays out Five Worlds that we could be living in.

### What might a proof (not) look like?

In the core part of this seminar, we will discuss several approaches to the P versus NP problem, and discuss *barriers*, that is, formal reasons why decades of research have not resulted in much progress on the question. In particular, we will roughly follow the survey paper by Aaronson.

### Would quantum computers help?

We will debunk common myths and misconceptions.

- Quantum computers probably don’t help to solve NP-complete problems
- Computing the prime factors of an integer is probably not NP-complete
- Even if P≠NP holds, this does not mean that cryptography is safe

## Workload and Grading

- The date of the first meeting will be determined by a doodle poll.
- We will meet a few times during the semester and develop a common overview of the topic.
- At the end of the semester, every student will give a
*talk*:- Talks can be given in German or English
- Students are allowed to collaborate on larger topics, but each student should speak for about 45 minutes.
- Students taking the seminar as a Proseminar can choose a less technical topic
- All students will be asked to submit a short paper (“Ausarbeitung”) on their topic (~5 pages)

## Prerequisites

**Required course: Theoretische Informatik**

Optional: Crypto, Algorithms, Complexity

Language: German or English

## References

Three of Impagliazzo’s Five Worlds as pictured by Thore Husfeldt

(released under CC BY-SA 3.0)