Erich Rast - P=NP

Veronica öffnete die Emails aus dem NSANet. Sie überflog die Ankündigungen von Gottesdiensten, ein Rundschreiben des Direktors, das keine nennenswerten Informationen enthielt, und eine obligatorische Einladung zur hauseigenen Weihnachtsfeier mit den ›Fellow Nerds‹, der sie sowieso nicht entgehen konnte. Was diese anging, hoffte sie nur inständig, dass keiner auf die Idee kam, wieder eine ›Schlüsselparty‹ zu veranstalten. Die Sache war die: Der Puzzlepalast förderte Beziehungen und Heiraten auf geradezu aggressive Weise, solange sie im eigenen Haus blieben, weil ledige Männer nämlich als Sicherheitsrisiko galten. Also verschwendeten findige Köpfchen in der Personalabteilung eine Menge Hirnschmalz darauf, die Mitarbeiter bei sozialen Ereignissen wie Weihnachtsfeiern zusammenzubringen. Eine einzige Kuppelshow. Nun arbeitete Veronica allerdings in einer Abteilung, die so ziemlich die nerdigsten, verstocktesten und hochbegabtesten Mathematiker beherbergte, die es auf der Welt gab, und darunter fanden sich nur sehr, sehr wenige Frauen. Dieses Verhältnis hatte sich seit ihrem Studium leider nie geändert, und auch wenn den meisten Kollegen nicht im Traum eingefallen wäre, sie auf eine Weise zu behandeln, die man als politisch unkorrekt missverstehen konnte, waren die kleinen Feiern und Feste in der Abteilung mitunter etwas gezwungen und anstrengend. Sie klickte die Mails beiseite, musste als Leiterin diverser Arbeitsgruppen sowieso vorbeischauen, und ihr Blick fiel auf eine Mail, die von TAO stammte. ›TAO‹ stand für ›Tailored Access‹, das waren die Typen, die sich in jedes beliebige System einhackten, um seinen Benutzer auszuspionieren. Das jedoch war nicht der Grund, weshalb die Nachricht ihre Aufmerksamkeit erregte, sondern ihr Titel: P=NP?

Sie schmunzelte. Wollte da wieder einmal jemand wissen, ob P=NP war? Das war eines der wichtigsten ungelösten Probleme der theoretischen Informatik. Es ging um sogenannte Komplexitätsklassen. Die Frage war, ob die Klasse der Algorithmen, die in polynomialer Zeit abliefen, mit der Klasse der Algorithmen identisch war, die in nichtdeterministischer polynomialer Zeit abliefen. Wenn sie diese Definition den Mitarbeiter anderer Behörden auf externen Schulungen anbot, dann erntete sie zur Antwort im Allgemeinen bloß ein dummes Stieren. Deshalb hatte sie sich im Lauf der Jahre darauf verlegt, das Problem in einfachere, wenn auch nicht unbedingt korrekte Worte zu fassen. Programme in der Klasse P konnten mitunter recht langsam laufen, aber sie waren normalerweise von modernen Computern bewältigbar. Programme in der Klasse NP hingegen schienen eine Laufzeit zu haben, die weitaus ungünstiger war, sie wuchs oft sogar exponentiell mit der Zahl der Eingaben, sodass sie für größere Mengen an Eingabevariablen in kürzester Zeit praktisch nicht mehr berechnet werden konnten. Die These P=NP besagte nun, dass es für Probleme der Klasse NP einen Algorithmus gab, der sie in der vertretbaren Laufzeit eines P-Problems löste. Weder einen Beweis noch einen Gegenbeweis für diese Behauptung hatte man bis zum heutigen Tag gefunden. Die Frage im Titel der Nachricht von TAO brachte sie zum Schmunzeln, weil praktisch alle Mathematiker innerhalb und auch außerhalb der Behörde, ja auf der ganzen Welt, der Meinung waren, dass P ungleich NP war, dass es keine Übersetzung von NP-Problemen in P-Probleme gab, und dass letztere tatsächlich eine Klasse schwieriger waren und auf einem Computer bei entsprechend vielen Eingabevariablen bis zum Ende des Universums nicht gelöst werden konnten. Alles wies auf P≠NP hin, auch wenn es sich als erstaunlich schwer herausgestellt hatte, diese These zu belegen. Die NSA jedenfalls hatte noch keinen Beweis gefunden, dabei hätte sie durchaus einen gebrauchen können. Falls nämlich jemand einen für P=NP fand, dann bräche dieser zumindest theoretisch die gängigen Verschlüsselungsalgorithmen mit einem Schlag. Nicht, dass Veronica oder irgendjemand sonst im Puzzlepalast das für möglich hielt. Einige ihrer Mitarbeiter glaubten sogar, dass zwar P≠NP der Fall sei, dass diese Behauptung aber prinzipiell nicht bewiesen werden konnte. Kurz gesagt, der Kollege von TAO hatte die falsche Frage gestellt. Er hätte wenigstens ›P≠NP?‹ wählen sollen.

Sie öffnete die Nachricht und überflog sie mit gerunzelter Stirn. Eine Reihe von Emails und Chataufzeichnungen waren angehängt, die von jemandem stammten, der angeblich dieses berühmte offene Problem gelöst hatte, und der Kollege von TAO wollte von ihr erfahren, ob da was dran war. Sie seufzte. Als ob das so einfach wäre! Natürlich prüfte sie solche Beweisversuche nicht zum ersten Mal und sie war in der Tat auch die richtige Ansprechpartnerin, weil sie die letzte Forschungsgruppe zu dem Thema geleitet hatte, bis die Versuche wieder einmal mangels Erfolg eingestellt worden waren. Sie kannte sämtliche angeblichen Beweise von P=NP, hatte schon dutzende wenn nicht gar hunderte gesehen, und natürlich hatten sich bisher alle als falsch erwiesen. Das Problem war nur leider, dass manche durchaus kompliziert sein konnten, und sie lieber bis zum nächsten Treffen der Algebraisierungsgruppe die Fachartikel gelesen hätte. Stattdessen durfte sie wieder einmal eine Liste von Punkten abarbeiten, die sie und ihre Mitarbeiter zusammengetragen hatten, um die Prüfung dieser Beweisversuche zu beschleunigen. Immerhin sprangen bei manchen Versuchen interessante Ansätze heraus, aber im Großen und Ganzen war diese Arbeit monoton, zumal das Ergebnis ihrer Meinung nach ohnehin feststand. Mathematiker von Rang und Namen, die tatsächlich glaubten, dass P gleich NP war, konnte man an einer Hand abzählen.

Bevor sie sich über die Exzerpte hermachte, besorgte sie sich in einer von mehreren Kantinen im Gebäude einen Becher Kaffee. Offene Getränke waren nicht gerne gesehen, immerhin enthielt einer der Rechner teure Spezialelektronik, die vielleicht sogar in der hauseigenen Chipfabrik hergestellt worden war, und in vielen Bereichen mit sensibler Technik war der Genuss von Getränken und Speisen streng verboten. Aber R12 war ja eine reine Forschungsabteilung, und noch dazu eine, die nichts mit Hardware am Hut hatte. Veronica rauchte nicht, ernährte sich im Vergleich zu so manch anderem, den sie kannte, sehr gesund und joggte regelmäßig, doch wie die meisten Kollegen hatte sie sich das unerklärliche, heftige, in regelmäßigen Abständen auftretende Verlangen nach Koffein niemals abgewöhnen können. Der Abteilungsleiter Colonel Lewis verstand die Bedürfnisse seiner Mitarbeiter. Wie er einmal bei einem Treffen angemerkt hatte, müsse man ihm seine Lieblingstasse mit dem NSA-Emblem – einem Adler, der das amerikanische Wappen als Schild vor der Brust trug – erst aus seinen kalten, toten Händen ringen, bevor man unter seiner Aufsicht ein Kaffeeverbot durchsetzen konnte. Er war in der Abteilung sehr beliebt.

Sie nahm einen Schluck und studierte die Aufzeichnungen. Das Datenmaterial erwies sich als dürftig. Der Kollege von TAO hatte nicht mehr als ein paar Emails mitgeschickt, deren Metadaten und Adressen automatisch entfernt und bereinigt worden waren, sowie zwei Konversationen aus einem Webforum, das Veronica nicht kannte, obwohl sie mit den meisten englischsprachigen Foren zur Mathematik vertraut war und sie gelegentlich überflog, ohne selbst Kommentare abzugeben. Das sah schon gleich nach einem typischen Fehlzünder aus, denn ernstzunehmende Forscher trieben sich selten auf Internetforen herum. Um in der Mathematik auf internationalem Niveau ganz vorne mit dabei zu sein, brauchte man Zeit, sehr viel Zeit, und musste jede Ablenkung vermeiden. Überhaupt war es ungewöhnlich, dass die Anfrage von TAO kam, statt wie üblich von einem Analytiker oder einer außenstehenden Agentur.

Sie seufzte und holte aus einem verschlossenen Aktenschrank die Checkliste, die sie selbst zusammen mit Kollegen in der ›Arbeitsgruppe Komplexität‹ entwickelt hatte. Diese Gruppe hatte sie vier Jahre lang geleitet, sie stellte den letzten ihr bekannten Versuch dar, das P=NP Problem zu lösen; der Höhepunkt einer Reihe solcher Projekte seit der Gründung der NSA im Jahr 1952, bei denen eine Menge interessanter Techniken und verbesserte Methoden zur Primfaktorisierung herausgesprungen waren und doch keiner dem Ziel nahegekommen war, einen Beweis zu finden. Die Liste fasste die Details zu drei bekannten Hürden zusammen, mit denen jeder Versuch zu kämpfen hatte, P≠NP und verwandten Sätzen der theoretischen Informatik zu beweisen. Ihrer Erfahrung nach stolperten über neunzig Prozent aller Beweisversuche über die drei Hürden auf dieser Liste. Sie arbeitete die beiden Emails durch, sie waren lang, doch es mangelte ihnen an Details, und merkte schnell, dass sie es mit einem begabten Profi zu tun hatte. Zumindest aus den angedeuteten Methoden ließ sich schließen, dass dem Autor die üblichen Probleme und die Varianten der drei Hürden, die in der zivilen Mathematik umliefen, bekannt waren. Die NSA hatte intern im Lauf der Jahrzehnte eine Menge zusätzliches Wissen angesammelt, sie selbst hatte rund zwei Jahre in Teilzeitarbeit gebraucht, um sich in das geheimgehaltene Material einzuarbeiten, doch auch diesem schienen die Versuche des Autors zumindest nicht direkt zu widersprechen, denn er kombinierte einige sehr ungewöhnliche Bereiche, fortgeschrittene Techniken aus der algebraischen Topologie und Methoden aus der theoretischen Physik, die mit Entropie und Thermodynamik zusammenhingen und die sie selbst weniger gut kannte. Außerdem versuchte er nicht P=NP direkt zu beweisen, was bei Laienversuchen fast immer zu Problemen führte, sondern hatte sich ein verwandtes Theorem zu randomisierten Algorithmen zum Ziel genommen, das schon allein von der Struktur her mehr Erfolg versprach. Je mehr sie von seinen Ausführungen las, desto mehr wunderte sie sich, ob sie den Autor vielleicht kannte. In den Aufzeichnungen war jeder Hinweis auf seinen Namen durch das Pseudonym ›HONIGDACHS‹ ersetzt worden, und sein Gesprächspartner hieß ›RUBIN‹. Wer war HONIGDACHS? Jedenfalls kein Dummkopf, dachte sie sich. Solche direkten Transkripte, die kaum redigiert worden waren, bekam sie selten zu Gesicht, und sie musste zugeben, dass von ihnen eine gewisse Faszination ausging. Aus den eher skeptischen Antworten von RUBIN schloss sie, dass er an einer Uni lehrte, der Wortwahl und dem Stil nach war er wohl ein junger amerikanischer Sprecher, ein Assistenzprofessor etwa, der an dem Thema arbeitete und oft Mails mit Beweisversuchen bekam. Er nahm HONIGDACHS ernst und bot ihm an, das Paper mit dem eigentlichen Beweis zu prüfen, was bei diesem Thema keine Selbstverständlichkeit war, und doch war ihm die Skepsis anzumerken. Enttäuscht stellte Veronica fest, dass die Konversation mit einem kurzen Austausch von Höflichkeiten und ein paar Tipps zum weiteren Vorgehen verfrüht endete. Den Beweisversuch selbst hatte HONIGDACHS nicht angehängt, und die Auszüge aus den Foren erwiesen sich als viel zu allgemein formuliert, um nennenswerte Hinweise zu liefern.