Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

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/