Komplexitätstheorie im Netz

• Ein Turing Maschinen Applet von David Eck.

• Das Halteproblem ist unentscheidbar, erklärt von Mark Jago (Dep. of Philosophy, University of Nottingham, UK).

• Alan Turing Homepage.

• Ein kleines PCP mit langer Lösung.

• Eine Liste unentscheidbarer Probleme findet man auf Wikipedia. Etwas ausführlicher ist der Artikel von Bjorn Poonen.

• Motivation für das P vs. NP Problem

• Der Status des P versus NP Problems, ein Übersichtsartikel von Lance Fortnow, Communications of the ACM, September 2009.

• Der Orginalartikel The Complexity of Theorem-Proving Procedures von Steven Cook, erschienen in den Proceeedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), 1971.
  Tim Rohls hat die Arbeit in TEX-Format gebracht

• Nach Cook's Artikel veröffentlichte Richard Karp 1972 die erste Liste mit mehreren NP-vollständigen Problmen.
  Der Orginalartikel Reducibility among Combinatorial Problems von Richard Karp, Complexity of Computer Computations, Computer Applications in the Earth Sciences, pp. 85-103, Springer, 1972.

• Bei der 3-Punkte Regel im Fußball bekommt der Gewinner eines Spiels 3 Punkte und der Verlierer 0 Punkte. Bei einem Unentschieden bekommen beide Mannschaften je 1 Punkt.
  Nachdem schon einige Spiele der Saison gespielt sind, möchte man beim Fußball Eliminations Problem wissen, ob ein bestimmter Verein noch Meister werden kann.
  Thomas Hofmeister hat mit seiner Gruppe gezeigt: das Fußball Eliminations Problem mit der 3-Punkte Regel ist NP-vollständig.

• Im Electronic Colloquium on Computational Complexity (ECCC) findet man Forschungsberichte, Übersichtsartikel, Bücher und viele weitere interessante Links.

• Die Cornell University betreibt ebenfalls eine Plattform für Forschungsberichte, arXiv.
• Der Computational Complexity Blog von Lance Fortnow und Bill Gasarch.

• Ein effizienter Primzahltest von Manindra Agrawal, Nitin Saxena and Neeraj Kayal vom IIT Kanpur, Indien. Für diese Arbeit erhielten sie den Gödelpreis 2006.

  Siehe auch die Geschichte der Primzahltests und die Primzahlseite.

• Die Gesellschaft für Informatik (GI) ist ein Verein zur Förderung der Informatik in Deutschland. Die GI ist in 10 Fachbereiche untergliedert. Theoretische Informatik ist im Fachbereich Grundlagen der Informatik angesiedelt.

• European Association for Theoretical Computer Science (EATCS)

• Grundlagen der Informatik gelten als schwierig und sind bei Studenten oft unbeliebt. Hier die Meinung mehr oder weniger unverdächtiger Personen zum Thema:
  • Matthias Jarke, GI-Präsident
  • Rick Rashid, Microsoft Senior Vice President, Research