Seminar: Komplexität und Kryptologie
Hürden zum Lösen des P-NP-Problems
Termin: | SE Mi 11-13 (RUD 26, 1'303) ACHTUNG: Zeit geändert! Prof. Johannes Köbler, Sebastian Kuhnert |
Zuordnung: | Hauptstudium, Seminar |
Seminarankündigung (überarbeitet) |
Inhalte und Lernziele
Das P-NP-Problem ist eine der größten offenen Fragen der Theoretischen Informatik: Über mehrere Jahrzehnte ist es nicht gelungen, einen Beweis für die Gleichheit oder die Ungleichheit dieser beiden Komplexitätsklassen zu finden.
In letzter Zeit konnten aber einige Hürden ausfindig gemacht werden,
die solchen Beweisen entgegenstehen: Sie dürfen weder natürlich
sein, noch relativieren oder algebrieren. In diesem
Seminar werden wir uns mit den Konzepten beschäftigen, die sich hinter
diesen Begriffen verbergen. Außerdem werden Techniken vorgestellt, mit
denen zumindest manche dieser Hürden überwunden werden können.
Themen für Referate und Termine
- Einführung
Sebastian Kuhnert, 23.4. und 30.4. [Folien]
- Weder P = NP noch P ≠ NP kann mit relativierenden Techniken
bewiesen werden
Quellen: [Pap95, Kapitel 14.3]
Martin Stigge, 7.5.
- IP = PSPACE: Ein nicht-relativierender Beweis
Quellen: [She92], [DK00, Kapitel 10.1], [AB07, Kapitel 8.5], [FS88]
Martin Schröder, 21.5.
- Arthur-Merlin Games: Varianten von interaktiven
Beweissystemen
Quellen: [DK00, Kapitel 10]
Stefan Klumpp, 4.6.
- Weder P = NP noch P ≠ NP kann mit algebrierenden Techniken
bewiesen werden
Quellen: [AW08, insbes. Abschnitte 1, 2, 5.1]
Sebastian Kuhnert, 13.7.
Empfohlene Literatur
- [AB07]
Arora, Sanjeev, und Boaz Barak. Complexity Theory: A Modern Approach.
Web draft. Princeton University, 2007.
http://www.cs.princeton.edu/theory/complexity/ - [AW08]
Aaronson, Scott, und Avi Wigderson. »Algebrization: A New Barrier in Complexity Theory«.
In: Electronic Colloquium on Computational Complexity (5 2008). ISSN 1433-8092.
http://eccc.hpi-web.de/eccc-reports/2008/TR08-005/ - [DK00]
Du, Ding-Zhu, und Ker-I Ko. Theory of Computational Complexity.
New York, NY, USA: John Wiley & Sons, Inc., 2000. - [FS88]
Fortnow, Lance, und Michael Sipser. »Are There Interactive Protocols for co-NP Languages?«.
In: Information Processing Letters 28.5 (Okt. 1988). 249–251. ISSN 0020-0190.
http://people.cs.uchicago.edu/~fortnow/papers/conpipl.ps - [Gol01]
Goldreich, Obed E. Foundations of Cryptography. Bd. 1: Basic Tools.
Cambridge University Press, 2001. ISBN 0-521-79172-3. - [Pap95]
Papadimitriou, Christos H. Computational Complexity.
Reading, Mass.: Addison-Wesley, 1995. ISBN 0-201-53082-1. - [RR97]
Razborov, Alexander A., und Steven Rudich. »Natural Proofs«.
In: Journal of Computer and System Sciences 55 (1 1997). 24–35. ISSN 0022-0000.
http://dx.doi.org/10.1006/jcss.1997.1494 - [She92]
Shen, Alexander. »IP = PSPACE: Simplified Proof«.
In: Journal of the ACM 39.4 (Okt. 1992). 878–880. ISSN 0004-5411.
http://doi.acm.org/10.1145/146585.146613 - [Zoo]
Complexity Zoo.
http://www.complexityzoo.com/