Lemmings ist np vollständig

Ort: Kaffeeküche des Instituts für Theoretische Informatik, Universität Bonn
Zeit: Ein verregneter Nachmittag im November 1994

(In der Ecke brummt ein IBM PS/2. Rainer, Anfang 30, kurbelt aufgeregt am Manuskript-Stapel in seinen Händen. Thomas, Ende 40, gießt sich kochendes Wasser über seinen löslichen Kaffee.)

Rainer: Thomas, stell die Tasse weg. Das hier verändere die Informatik grundlegend! Ich habe letzte Nacht die korrigierten Fahnen meines Papers fertiggestellt. Der mathematische Beweis steht.

Thomas: (seufzt) Rainer, du hast drei Wochen lang nichts anderes getan als auf deinem Amiga diese kleinen Pixelmännchen mit grünen Haaren über den Bildschirm zu scheuchen. Sag mir bitte nicht, dass dein wissenschaftlicher Durchbruch auf Lemmings basiert.

Rainer: Genau das tut er! Hör zu. Ich habe das Wegfindungs- und Ressourcenallokationsproblem in Lemmings formalisiert. Überlegung: Du hast eine endliche Menge von Agenten, beschränkte Fertigkeiten – Basher, Builder, Blocker – und eine dynamische Topologie. Ich habe eine Reduktion konstruiert: Das allgemeine Lemmings-Entscheidungsproblem lässt sich direkt auf das Erfüllbarkeitsproblem der Aussagenlogik, auf 3-SAT, reduzieren!

Thomas: (blinzelt) Du hast bewiesen, dass ein Computerspiel von DMA Design NP-hart ist?

Rainer: Genau! Besser gesagt: Das Lösen eines Lemmings-Levels in optimaler Zeit ist ein Problem aus der Klasse der NP-harten Probleme. Da P!=NP gilt – und davon gehen wir alle aus –, gibt es keinen Algorithmus, der in polynomieller Zeit die optimale Route für beliebig große Level berechnen kann. Die Zahl der möglichen Zustände wächst exponentiell. Ein Rechner bräuchte für ein komplexes Level mehr Rechenschritte, als es Atome im Universum gibt!

Thomas: Schon faszinierend, Rainer. Eine nette mathematische Spielerei für die Zeitschrift für Angewandte Mathematik. Aber warum schaust du mich an, als hättest du gerade das Feuer erfunden?

Rainer: Weil die Implikation gigantisch ist! Bedenke doch, was die KI-Enthusiasten in MIT und Stanford behaupten: Sie wollen ein System bauen, das die menschliche Kognition simuliert. Sie träumen von "intelligenten Agenten", die reale Umgebungen analysieren, Entscheidungen in Echtzeit treffen und Probleme lösen.

Thomas: Und wo ist der Widerspruch?

Rainer: Die reale Welt ist um ein Vielfaches komplexer als ein zweidimensionales Lemmings-Raster! Ein dreijähriges Kind schaut auf den Bildschirm, sieht die Gruben und Hindernisse und begreift innerhalb von zwei Minuten intuitiv, wie es drei Lemminge retten kann. Ein menschliches Gehirn löst dieses NP-harte Problem spontan, durch Intuition, Gestaltwahrnehmung und heuristisches Verständnis.

Thomas: Der Mensch nutzt eben Faustregeln, Rainer. Keine exakten Berechnungen.

Rainer: Aber ein Computer kann nur exakt rechnen! Er hat kein Bewusstsein, keine Intuition. Er muss den Zustandsraum absuchen. Wenn ein Algorithmus schon an einem deterministischen, hochgradig vereinfachten 256x128-Pixel-Level mathematisch an der exponentiellen Laufzeitmauer zerschellt, wie soll eine Maschine je die chaotische, kontinuierliche Realität erfassen?

Thomas: Er könnte Approximationen nutzen. Künstliche Neuronale Netze, wie Rumelhart und McClelland sie beschreiben...

Rainer: (winkt ab) Ach, Backpropagation! Das sind doch nur lineare Algebra-Tricks auf Supercomputern. Wenn das zugrundeliegende Entscheidungsproblem der Welt NP-hart ist, verfängt sich jedes neuronale Netz in lokalen Minima oder braucht unendlich lange zum Konvergieren. Ein Computer kann niemals "denken", weil Denken bedeutet, NP-harte Strukturen ohne exponentiellen Rechenaufwand zu durchdringen. Meine Arbeit zeigt klar: Eine echte Künstliche Intelligenz ist auf siliziumbasierten Architekturen mathematisch unmöglich. Es ist eine funktionale Sackgasse!

Thomas: (schaut auf den Stapel) Und du meinst wirklich, die Gutachter nehmen eine AI-Widerlegung auf Basis von Pixel-Tieren an?

Rainer: Die Mathematik ist unbestechlich, Thomas! Ich habe 40 Seiten Reduktionsbeweise mit Schaltelementen und Tunnel-Gadgets geführt. Wenn die Redaktion das akzeptiert, ist der KI-Hype der letzten Jahrzehnte offiziell widerlegt. Wir können die Lehrstühle für Expertensysteme dichtmachen und das Geld wieder in die ehrliche, mathematische Numerik stecken.

Thomas: Nun gut. Aber bevor du die KI-Forschung abschaffst: Kann dein Beweis mir erklären, wie ich Level 12 auf dem Amiga schaffe? Ich hänge da seit Montag.

Rainer: (schmunzelt) Das ist das Schöne daran: Nein. Du musst dein Gehirn benutzen, Thomas. Denn eine Maschine wird es für dich niemals ausrechnen können.