MESOPOTAMIA NEWS : KEIN OSTERN IN SICHT = TOTALE ERFASSUNG & FORMELLE SUBSUMTION DER TRANSHUMANEN MODULE
Das Problem aller Probleme – Von Dietmar DATH
– ….. „ Die menschliche Kreativität verliert damit allerdings ihr Salz, und auch Verschlüsselungen werden sinnlos. Was eine „P=NP”-Welt außerdem für die Wahlbeeinflussung und die Politik bedeuten würde, ahnen wir ja gerade schon.“
Was können Computer eigentlich nicht? Die Digitalisierung ist eine Wette, die sich in einer sehr komplexen Frage für eine von zwei Antworten entscheidet.
Vier Männer sitzen an einem Tisch und diskutieren ein Dokument. Ein fünfter hat es mit-gebracht, er arbeitet für den Staat. Die vier sollen das Dokument unterschreiben, das einerseits fixiert, wie sie für eine Entdeckung belohnt werden, die sie gemacht haben, und damit andererseits ihre Urheberschaft an ihr feststellt. Die vier merken schnell, dass die Anerkennung sie nicht nur als Genies identifiziert, sondern gleichzeitig vorsorglich als Sündenböcke markiert, falls jemand mit dem, was sie entdeckt haben, die gesamte hochtechnisierte Zivilisation der nachindustriellen Weltgesellschaft zerstören sollte.
Wie wichtig ist das, was sie entdeckt haben? Einer von ihnen wird deutlich: Die letzte ähnlich folgenreiche Entdeckung der Menschheit war, sagt er, „das Feuer”. Der faszinierende Spielfilm „Travelling Salesman” (2012) von Timothy Lanzone, aus dem diese Szene stammt, ist ein Kammerspiel über Mathematik, Computer und Verantwortung. Anderthalb Stunden wird fast nur geredet. Der Stoff, von dem aus dieses lange Gespräch auf riesige Themen zugreift, ist das größte Rätsel der theoretischen Informatik —das Problem, das alle Probleme haben, die man rechnen kann. Der Fachname dafür lautet: „Ist P gleich NP oder nicht?”
P und NP sind Namen für Komplexitätsklassen von Problemen. Eine Klasse ist ein Haufen nicht exakt eine „Menge“). Komplexität bedeutet dabei Rechenaufwand: Wie lange braucht ein Apparat, um eine gesuchte Größe zu finden? P steht für „polynomiell”. So nennt man hier eine Rechenzeit, deren Wachstum auf einem nach eindeutigen Schritt-für-Schritt-Regeln arbeitenden Gerät “‘von einer Polynomfunktion beschrieben wird. So eine Funktion lässt sich, wie der Name sagt, als Polynom notieren, das heißt als endliche Summe von Ausdrücken, die Variablen enthält, deren Exponenten ausschließlich natürliche Zahlen sind, also Zahlen, die man an Fingern und Zehen (genügend davon vorausgesetzt) abzählen kann. In der Klasse P sind damit alle Probleme enthalten, für deren Lösung es einen diese polynomielle Komplexität aufweisenden Algorithmus gibt.
Algorithmen sind, verglichen mit anderen Sorten Software, überschaubar — zum Vergleich: Das Betriebssystem von Microsoft, Vista, frisst hundert Millionen Zeilen Programmcode, während die schönsten Algorithmen auf eine Postkarte passen.
Die Algorithmen in P sind deterministisch, das heißt: Jeder Rechenschritt ist von ihren Vorschriften erschöpfend bestimmt. Die Klasse NP dagegen enthält Probleme, die zwar gerechnet werden können, aber nicht deterministisch: Die Arbeitsweise kann sich unterwegs zur Lösung ändern.
Wer diese Definitionen von P und NP zu kompliziert findet, kann sich’s vergröbert merken: Zu P gehören Probleme, deren Lösung man leicht findet, zu NP dagegen solche, bei denen man leicht überprüfen kann, ob die Lösung, wenn man denn eine hat, auch wirklich eine ist.
Wenn P=NP gelten würde, hieße das: Alle scheinbar schwierigen Probleme sind nur einfache, deren Einfachheit man noch nicht einsieht. Es gibt also für sie garantiert je mindestens einen Algorithmus, man kennt ihn nur noch nicht. Sollte das Herausfinden etwa eines Passworts oder der richtigen Zahl für ein leeres Sudoku-Feld wirklich genauso einfach sein wie die Überprüfung, ob man das richtige Passwort (man gibt’s halt ein, schon geht das Konto auf) oder die richtige Sudoku-Zahl (man zählt halt nach) gefunden hat?
Ist es nicht prinzipiell einfacher, Lösungen zu überprüfen, als sie zu finden? Das müsste so sein, meint die Alltagsintuition, und die Fachgemeinschaft hat, wie der Informatiker Richard J. Lipton sagt, zusammen mit allen, die auf „Digitalisierung” setzen, sozusagen eine Wette darauf abgeschlossen, dass diese Intuition stimmt.
Exakte Wissenschaft aber darf sich damit nicht zufriedengeben, denn wie sie weiß, gibt es vieles, was unsere Intuition nahelegt, was aber dennoch nicht stimmt. Das fängt bei so banalen Sachen wie dem Durchschnitt an — man kann den Durchschnitt einer Kenngröße in zwei Mengen von Objekten, die diese Größe aufweisen, gleichzeitig heben, indem man nur ein Objekt aus der einen in die andere Menge verschiebt —und endet noch lange nicht bei Absonderlichkeiten wie der Tatsache, dass das Denken eine Kugel so auseinandernehmen und zu zwei Kugeln wieder zusammensetzen kann, dass beide gleich viel Volumen haben wie die ursprüngliche Kugel („Satz von Banach und Tarski”).
Etwas beweisen heißt in der Mathematik nicht: „Es ist so, weil”, sondern „Es kann gar nicht anders sein, weil” (zum Beispiel weil die Gegenannahme zu einem Widerspruch führt oder weil eine Größe, deren Existenz der Beweis behauptet, konstruktiv gefunden ist). Im Jahr 2000 hat das Clay Mathematics Institute in Cambridge (Massachusetts) für die Lösung von sieben mathematischen Fundamentalproblemen ein Preisgeld von jeweils einer Million Dollar ausgesetzt, darunter eine 2002 schließlich bewiesene Vermutung von Poincarè über Kugeln in mehreren Dimensionen, die Frage nach Lösungen für die Navier-Stokes-Gleichungen, die turbulente Vorgänge in der Strömungslehre beschreiben, die Yang-Mills-Gleichungen der Hochenergiephysik und eben das P/NP-Problem, von dem Cristopher Moore und Stephan Mertens in ihrem Grundlagenwerk „The nature of computation” (2011) sagen, es sei fundamentaler als alle anderen Clay-Preisprobleme zusammen, denn: „Kugeln, Turbulenzen und Elementarteilchen sind zwar wichtige mathematische und physikalische Objekte, die uns vor tiefe und schwierige Probleme stellen. Aber die P/NP-Frage handelt von der Natur des Problemlösens selbst.”
Nüchterne Menschen geraten ins Schwärmen, aber auch in schlechte Träume, wenn sie darüber spekulieren, was eine Lösung von P/NP bedeuten würde. In seinem mit vielen verständlichen Beispielen bestückten Buch „The Golden Ticket” (2013) — der besten populären Einführung in P/NP, die es bislang gibt — entwickelt der Computerwissen-schaftler Lance Fortnow das fiktive Szenario eines Algorithmus, der NP-Probleme in P-Probleme übersetzt und damit ein konstruktiver Beweis für „P=NP” ist.
Die erste Fassung dieses Algorithmus ist noch kompliziert, aber er optimiert sich danach gewissermaßen selbst und gleicht dann, wie Fortnow schreibt, nicht etwa einem Flaschengeist, der einen Wunsch erfüllt, sondern einem, der alle Wünsche nach Ergebnissen von Suchvorgängen erfüllen kann — von der Krebstherapie (individuelles Design von Proteinen, die sich auf genau die richtige Art falten, um die Krebszellen auszuhungern, aber gesunde Zellen in Ruhe lassen — der Krebs wird dann einfach aus dem Körper gewaschen) bis zum Flugzeugflügeldesign.
Die menschliche Kreativität verliert damit allerdings ihr Salz, und auch Verschlüsselungen werden sinnlos. Was eine „P=NP”-Welt außerdem für die Wahlbeeinflussung und die Politik bedeuten würde, ahnen wir ja gerade schon. Nicht nur ein „P=NP”-Beweis freilich hätte weitreichende Folgen, sondern auch der Beweis des Gegenteils, der uns mitteilen würde, dass das, was Computer können, erstens grundsätzlich und zweitens in alle Ewigkeit begrenzt ist.
Denn schon auf dem Weg dahin würde man vieles darüber lernen, was Problemlösen überhaupt ist. So war es bei allen bisherigen Versuchen, P/NP zu klären, auch wenn die Ankündigungen, es sei gelungen, einen der beiden Sätze zu beweisen, sich bislang stets als voreilig erwiesen, selbst in so vielversprechenden Fällen wie dem des Hewlett-Packard-Mathematikers Vinay Deolalikar 2010 oder zuletzt seines Bonner Kollegen Norbert Blum 2017. Im Fernsehen ist der reine Tor Homer Simpson schon im Jahr 1995 im virtuellen Raum der großen Wahrheiten an „P=NP” vorbeispaziert, während in einer anderen Trickfilmserie, „Futurama”, fünf Jahre später zwei Ordner im Regal standen — einer hieß „P” und einer „NP”, zum Glück sauber getrennt.
Die geistreichste und bewegendste künstlerische Annäherung ans rationale Mysterium „P/NP” ist ein Comic: In „The Vision” (2016), verfasst von Tom King, illustriert von Gabriel Hernandez Walta und Michael Walsh, wird nicht nur auf knapp vier Seiten (bebildert mit einem Hund, der ein Geheimnis ausgräbt) „P/NP” erklärt, sondern außerdem die existentielle Bedeutung des Problems für Wesen, die denken können, in Form der Geschichte eines Androiden erzählt, der von einem Schurken als Killer programmiert wurde. Er widersetzt sich dem Programm, um „wie ein Mensch” zu leben — obwohl das bedeutet, Dinge anzunehmen, die sich weder beweisen noch widerlegen lassen und also, streng positivistisch’ betrachtet, sinnlos sind. Als seine Frau ihn auf diesen Tatbestand hinweist, sagt der Androide: „Etwas für wahr zu halten, was der Logik nichts bedeutet, ist die Kernaufgabe des Menschen. Die Verfolgung eines fixen Ziels mit logischen Mitteln ist die Vision meines Schöpfers. Das Streben nach einem unerreichbaren Ziel mit absurden Mitteln dagegen weist den Weg der Freiheit. Das ist meine Vision.”
Der Androide, der, entsprechend dieser Losung, „Vision” heißt, muss (wie jeder Mensch) rechnen und denken, um zu überleben. Ein Wesen mit Bewusstsein kann und darf nicht ausschließlich auf Instinkte und Intuitionen setzen: Wir können uns verbessern, nicht obwohl, sondern weil wir Fehler machen und sie erkennen. Kalküle sind fürs Menschliche notwendig. Aber sie reichen nicht.
DIETMAR DATH