- 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.
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)
Required course: Theoretische Informatik
Optional: Crypto, Algorithms, Complexity
Language: German or English
Three of Impagliazzo’s Five Worlds as pictured by Thore Husfeldt
(released under CC BY-SA 3.0)