Turing, NP-Vollständigkeit und P vs. NP: Eine Reise durch die Grenzen der Berechenbarkeit

Computation as a Universal and Fundamental Concept

Tim Roughgarden, Professor am Institute for Advanced Study, erklärt in diesem Kurs die fundamentalen Konzepte der Informatik: von Turings Entdeckung unentscheidbarer Probleme über algorithmische Abkürzungen wie den Dijkstra-Algorithmus bis hin zur Theorie der NP-Vollständigkeit und der P-vs-NP-Frage. Der Kurs zeigt, wie zwei Forschungstraditionen – eine über die Möglichkeiten von Algorithmen, die andere über ihre Grenzen – in dieser zentralen offenen Frage zusammenlaufen. Ohne Vorkenntnisse verständlich, beleuchtet er die Bedeutung für Kryptografie, KI und Quantencomputing.