Schedule

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.

Workload and Grading

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

Cryptomania Heuristica Algorithmica

(released under CC BY-SA 3.0)