Das Ungleichgewicht zwischen Ja und Nein

Was es mit dem Millennium-Problem „P versus NP“ auf sich hat

Der Exzellenzcluster MATH+ von FU, HU und TU Berlin sowie Weierstraß- und Zuse-Institut Berlin richtet am 1. Juli 2022 eine Veranstaltung der bundesweiten Reihe „Die 7 größten Abenteuer der Mathematik“ im Futurium aus. Gefeiert wird dort das sogenannte Millenniumsproblem „P versus NP“. Warum seine Lösung auch Auswirkungen auf unseren Alltag haben könnte und warum dieses Rätsel eine fundamentale Asymmetrie zwischen Ja und Nein offenbart, erklärt der Initiator Prof. Dr. Martin Skutella von der TU Berlin im Interview.

Herr Skutella, „P versus NP“ hört sich ziemlich kryptisch an. Warum haben Sie sich aus den sieben großen Rätseln gerade dieses rausgepickt, um es in Berlin zu präsentieren?

Zum einen, weil es gut hierher passt. Denn es ist ein Teil der Mathematik, die sich mit ganz konkreten Anwendungen beschäftigt. Etwa der Frage, wie die BVG ihre Fahrpläne noch besser organisieren könnte. Dieser Bezug zur Praxis ist ein Schwerpunkt der mathematischen Forschung in Berlin. Außerdem klingt das Problem zwar kompliziert, ich kann es aber selbst meinen Kindern im Prinzip leicht erklären.

Na dann mal los.

Ok, also: Es gibt eine bestimmte Menge von Problemen, bei denen es leicht ist, die Korrektheit einer gefundenen Lösung zu überprüfen. Wie bei einem Zahlenschloss. Sagt mir einer, die Lösung ist „3, 4, 7, 1“, kann ich das einfach einstellen und schauen, ob das Schloss auch wirklich aufgeht. Die Menge solcher Probleme nennen wir in der Komplexitätstheorie „NP“. Und dann gibt es noch eine Untermenge von NP, die nennen wir „P“. Das sind die Probleme, die sich leicht überprüfen lassen, und die dazu auch noch relativ leicht zu lösen sind. Das Zahlenschloss gehört da eher nicht dazu. Aber nehmen Sie zum Beispiel eine Kartei mit tausenden Fingerabdrücken bei der Polizei. Habe ich einen Fingerabdruck vom Tatort und will wissen, ob der in der Kartei schon vorhanden ist, gibt es dafür Suchalgorithmen. Die spucken mir innerhalb von Sekunden ein Ergebnis aus – die Lösung zu finden ist also leicht. Den vom Algorithmus in der Kartei gefundenen Abdruck kann ich dann von Hand mit dem vom Tatort vergleichen und so das Ergebnis überprüfen.

Und was haben die beiden Mengen jetzt Rätselhaftes miteinander zu tun?

Die große Frage ist, sind die beiden Mengen vielleicht identisch? Sind also alle Probleme, die sich einfach überprüfen lassen auch leicht zu lösen? Vielleicht haben wir einfach für die uns schwer erscheinenden Probleme in der Menge NP noch nicht den einfachen Lösungsweg gefunden, der sie dann auch zu Elementen von P machen würde. In dem Fall wäre P = NP.

Dann könnten Sie sich nicht mehr rausreden, wenn Sie keinen Algorithmus finden, der den BVG-Fahrplan besser macht, denn es muss ja einen geben…

Wenn die Fragestellung so ist, dass ich die Lösung einfach überprüfen könnte, ja. Ich beschäftige mich zum Beispiel mit sogenannten Approximationsalgorithmen für schwierige Probleme. Da finden wir dann immer „nur“ suboptimale Lösungen für praktische Anwendungen. Aber wir können manchmal mathematisch beweisen, dass diese suboptimale Lösung die beste Näherung ist an das Optimum, die wir überhaupt erreichen können. Und da drunter muss ich dann immer den Satz schreiben „Es sei denn, P = NP“. Das ist so ein ärgerlicher Schnipsel, den wir jetzt schon seit Jahrzehnten mit uns rumschleppen…

Verständlich, dass Sie den loswerden wollen. Aber so richtig wichtig ist das jetzt nicht, oder?

Oh, doch! Zum einen hätte P = NP extreme Konsequenzen für die Verschlüsselungstechnik, also auch für unseren Alltag mit EC-Karten und so weiter. Diese Technik beruht bisher darauf, dass es mathematische Probleme gibt, die die Funktionalität von Schlüssel und Schloss haben, also eine leicht überprüfbare Lösung, und die deshalb in NP liegen. Man kann sie aber hinreichend schwer machen, so dass sie für Außenstehende auch mit den besten Computern nicht zu knacken sind – sie liegen also nicht in P. Nur deshalb ist die Verschlüsselung sicher. Wäre nun aber die Menge P mit der Menge NP identisch, müsste zu all diesen bisher als unknackbar angesehenen Aufgaben zumindest theoretisch doch eine leicht zu öffnende Hintertür existieren.

Außerdem hat die Sache noch einen Clou. Um zu beweisen, dass P = NP ist, müsste man nur für ein einziges der schweren Probleme in NP einen einfachen Algorithmus finden. Zum Beispiel für das Hamilton-Kreisproblem. Dabei soll zum Beispiel in einem Eisenbahn-Netz eine Reihenfolge für den Besuch mehrerer Orte so gewählt werden, dass keine Station außer der ersten mehr als einmal besucht wird. Das ist verwandt mit dem Problem des Handlungsreisenden, haben Sie vielleicht schon mal gehört. Jedenfalls konnte man zeigen, dass alle uns bisher schwer erscheinenden Probleme in NP – und das sind Tausende! – miteinander verwandt sind. Hätte ich also einen einfachen Algorithmus für eines der Probleme gefunden, müsste ich den für die anderen nur etwas anpassen und hätte auf einen Schlag alle gelöst. Deshalb interessieren sich auch so viele Hobbymathematiker für das „P versus NP“-Rätsel.

Bundesweite Veranstaltungsreihe „Die 7 größten Abenteuer der Mathematik“

Die Veranstaltungsreihe läuft von Frühjahr bis Herbst. Im Mittelpunkt stehen dabei sieben mathematische Fragestellungen, die sogenannten Millennium-Probleme, für deren Lösung das Clay Mathematics Institute im Jahr 2000 jeweils eine Million US-Dollar Preisgeld in Aussicht stellte. Sie sind – mit nur einer Ausnahme, der Poincaré- Vermutung – bis heute ungelöst. Initiatoren der Veranstaltungsreihe sind die Junge Akademie und die Deutsche Mathematiker-Vereinigung (DMV), unterstützt werden sie von der Deutschen Forschungsgemeinschaft (DFG). Im Rahmen der Reihe organisieren verschiedene mathematische Forschungsstandorte Veranstaltungen zu je einem der Millennium-Probleme. MATH+ widmet sich dem Problem „P versus NP“.

MATH+ ist ein Exzellenzcluster

im Rahmen der Exzellenzstrategie und eine gemeinsame Einrichtung der drei großen Berliner Universitäten – Freie Universität Berlin, Humboldt-Universität zu Berlin und Technische Universität Berlin – sowie des Weierstraß-Instituts für Angewandte Analysis und Stochastik (WIAS) und des Zuse-Instituts Berlin (ZIB).

Wie definieren Sie eigentlich genau schwer und leicht bei diesen Problemen?

Leicht sind alle Aufgaben, bei denen die Zeit zur Lösung des Problems nicht exorbitant ansteigt, wenn ich das Problem etwas komplexer mache – also zum Beispiel 2000 statt 1000 Bushaltestellen im BVG-Fahrplan optimieren will. Mathematiker*innen reden da von einer polynomiellen Lösung. Ein schweres Problem wäre zum Beispiel eines, dessen Rechenzeit zum Erreichen der Lösung exponentiell mit der Anzahl der Bushaltestellen zunimmt. Alle Probleme, die ich nur durch stumpfes Ausprobieren lösen kann, sind zum Beispiel schwer.

Im Jahr 2017 gab es einen kleinen Medienrummel um den Bonner Informatikprofessor Norbert Blum. Der glaubte ja auch, das „P versus NP“-Rätsel gelöst zu haben. Der Hype hat allerdings nur 19 Tage gehalten…

Blum ist ein durchaus seriöser Experte auf dem Gebiet. Und er wollte auch nicht P = NP beweisen, wie viele andere, sondern genau das Gegenteil, nämlich dass die Mengen P und NP eben nicht gleich sind. Das ist übrigens auch genau das, was die meisten Mathematiker*innen und Informatiker*innen annehmen. Leider zeigte sich dann relativ schnell, dass es doch einen Fehler in seiner Beweisführung gab.

Könnten Sie zumindest ganz grob seine Idee schildern, die er bei diesem Beweisversuch hatte?

Ja, ich glaube das geht. Dafür muss man nur wissen, dass ich jeden Algorithmus umwandeln kann in einen logischen Schaltkreis für einen Computerchip. Dazu muss ich ihn zurückführen auf diese drei logischen Bausteine für Nullen und Einsen, mit denen Computer arbeiten. Zwei davon sind der AND- und der OR-Baustein. Die haben immer zwei Eingänge und einen Ausgang. Beim AND-Baustein müssen zwei Einsen ankommen, damit er am Ausgang auch eine Eins ausgibt. Beim OR-Baustein, also einem „Oder“, genügt dafür eine Eins auf einem der Eingänge. Und dann gibt es noch den NOT-Baustein, der hat nur einen Eingang und einen Ausgang und dreht einfach das Eingangssignal um: Aus einer Eins wird eine Null, aus einer Null eine Eins.

So, und jetzt ist es seit langem bewiesen, dass man dieses NOT unbedingt braucht, wenn die Rechenzeit zur Lösung eines Problems nicht exorbitant ansteigen soll mit seiner Größe, also etwa der Zahl der Bushaltestellen. Solche effizienten Lösungen liegen ja dann in P. Und Blum wollte zeigen, dass wenn es für jedes schwere Problem in NP doch eine effiziente Lösung gäbe, wenn also P = NP wäre, dass es dann auch eine Lösung geben müsste, die ohne das NOT auskommt. Und das wäre ein Widerspruch zu der Regel, dass man das NOT für effiziente Lösungen eben unbedingt braucht. Ergo muss P = NP falsch sein.

Und kommen dann diese ganzen ANDs und NOTs auch in dem Beweis vor?

Ja, tatsächlich. Der Beweisversuch ist 38 Seiten lang und enthält im Prinzip sogenannte Boolesche Algebra, die mit diesen logischen Operatoren arbeitet. Manche lernen das übrigens auch in der Schule, damit kann man sehr gut logische Knobelaufgaben lösen.

Sie meinen die von der Art: Wenn Klaus lügt, hat Gabi blonde Haare. Alle Schwarzhaarigen in der Klasse sagen immer die Wahrheit…

Genau. Es gibt übrigens auch noch einen tiefergehenden, fast philosophischen Aspekt, der mit diesem „P versus NP“-Rätsel zusammenhängt. Der hat auch mit dem NOT zu tun, das offenbar P von NP unterscheidet und ja eine Vertauschung von 1 und 0 vornimmt, oder von Ja und Nein. Bei der in der Menge NP geforderten Überprüfbarkeit der Lösungen gibt es nun offensichtlich ein Ungleichgewicht zwischen Ja und Nein, eine Asymmetrie. Nehmen Sie wieder das Zahlenschloss als Beispiel. Wenn Sie jemandem die Aufgabe geben „Baue ein Schloss, das mindestens eine Lösung hat“, dann kann mir diese Person die Erfüllung der Aufgabe sofort beweisen, indem sie das Schloss mit der Zahlenkombination „3, 4, 7, 1“ öffnet. Stellen Sie der Person aber die Aufgabe „Baue ein Schloss, das gar keine Lösung hat“, also quasi eine Negation, dann können Sie die Erfüllung der Aufgabe nur durch langwieriges Ausprobieren aller Zahlenkombinationen beweisen.

Das ist wie im richtigen Leben. Wenn mich jemand fragt „Kannst du nicht mal…?“, dann kann ich Ja sagen und es machen. Aber wenn ich Nein sage, wie soll ich jemals beweisen, dass ich es wirklich nicht kann und nicht einfach faul bin?

Das Interview führte Wolfgang Richter.