16.05.2018 16:00 Prof. Dr. Stefan Weltge (TUM, Antrittsvorlesung):
A Barrier to P=NP ProofsMI HS 3 (Boltzmannstr. 3, 85748 Garching)

The P-vs-NP problem describes one of the most famous open questions in mathematics and theoretical computer science. The media are reporting regularly about proof attempts, all of them being later shown to contain flaws. Some of these approaches where based on small-size linear programs that were designed to solve problems such as the traveling salesman problem efficiently. Fortunately, a few years ago, in a breakthrough result researchers were able to show that no such linear programs can exist and hence that all such attempts must fail, answering a 20-year old conjecture. In this lecture, I would like to present a quite simple approach to obtain such a strong result. Besides an elementary proof, we will hear about (i) the review of all reviews, (ii) why having kids can boost your career, and (iii) a nice interplay of theoretical computer science, geometry, and combinatorics.