Die 50-jährige Reise der Komplexitätstheorie an die Grenzen des Wissens | Quanta-Magazin

In der ersten Woche des Herbstsemesters 2007 schleppte sich Marco Carmosino zu einem Mathematikkurs, der für alle Informatik-Hauptfächer an der University of Massachusetts, Amherst, Pflicht ist. Carmosino, ein Student im zweiten Jahr, erwog, das College abzubrechen, um Videospiele zu entwickeln. Dann stellte der Professor eine einfache Frage, die sein Leben verändern sollte: Woher weiß man, dass Mathematik tatsächlich funktioniert?

„Das hat mich aufhorchen lassen und aufmerksam gemacht“, erinnert sich Carmosino, jetzt theoretischer Informatiker bei IBM. Er meldete sich für ein optionales Seminar über die Arbeit von Kurt Gödel an, dessen schwindelerregende selbstreferenzielle Argumente erstmals die Grenzen des mathematischen Denkens offenlegten und die Grundlage für alle zukünftigen Arbeiten zu den grundlegenden Grenzen des Rechnens bildeten. Es gab viel zu sehen.

„Ich habe es zu 100 % nicht verstanden“, sagte Carmosino. „Aber ich wusste, dass ich es wollte.“

Selbst erfahrene Forscher stoßen heute auf Verständnismangel, wenn sie sich mit der zentralen offenen Frage der theoretischen Informatik auseinandersetzen, dem so genannten P-NP-Problem. Im Wesentlichen geht es bei dieser Frage darum, ob viele Rechenprobleme, die lange als äußerst schwierig galten, tatsächlich leicht gelöst werden können (über eine geheime Abkürzung, die wir noch nicht entdeckt haben), oder ob sie, wie die meisten Forscher vermuten, wirklich schwierig sind. Auf dem Spiel steht nichts Geringeres als die Natur dessen, was erkennbar ist.

Trotz jahrzehntelanger Bemühungen von Forschern auf dem Gebiet der rechnerischen Komplexitätstheorie – der Untersuchung solcher Fragen über die intrinsische Schwierigkeit verschiedener Probleme – ist eine Lösung der P-gegen-NP-Frage immer noch schwer zu finden. Und es ist nicht einmal klar, wo ein möglicher Beweis beginnen soll.

„Es gibt keine Roadmap“, sagte er Michael Sipser, ein erfahrener Komplexitätstheoretiker am Massachusetts Institute of Technology, der sich in den 1980er Jahren jahrelang mit dem Problem auseinandergesetzt hat. „Es ist, als würde man in die Wildnis gehen.“

Es scheint, dass der Nachweis, dass Rechenprobleme schwer zu lösen sind, an sich schon eine schwierige Aufgabe ist. Aber warum ist es so schwer? Und wie schwer ist es? Carmosino und andere Forscher auf dem Teilgebiet der Metakomplexität formulieren Fragen wie diese als Rechenprobleme um und treiben das Feld voran, indem sie die Linse der Komplexitätstheorie auf sich selbst zurückdrehen.

„Man denkt vielleicht: ‚Okay, das ist irgendwie cool.‘ „Vielleicht sind die Komplexitätstheoretiker verrückt geworden“, sagte er Rahul Ilango, ein Doktorand am MIT, der einige der aufregendsten jüngsten Ergebnisse auf diesem Gebiet hervorgebracht hat.

Durch die Untersuchung dieser nach innen gerichteten Fragen haben Forscher herausgefunden, dass die Härte des Nachweises der Rechenhärte eng mit grundlegenden Fragen verknüpft ist, die auf den ersten Blick scheinbar nichts miteinander zu tun haben. Wie schwer ist es, versteckte Muster in scheinbar zufälligen Daten zu erkennen? Und wenn es wirklich schwierige Probleme gibt, wie oft sind sie dann schwierig?

„Es ist klar geworden, dass Metakomplexität im Mittelpunkt der Dinge steht“, sagte er Scott Aaronson, ein Komplexitätstheoretiker an der University of Texas, Austin.

Dies ist die Geschichte des langen und kurvenreichen Weges, der Forscher vom P-NP-Problem zur Metakomplexität führte. Es war keine einfache Reise – der Weg ist übersät mit falschen Abzweigungen und Straßensperren und er führt immer wieder auf sich selbst zurück. Doch für Metakomplexitätsforscher ist diese Reise in eine unbekannte Landschaft ihre eigene Belohnung. Fangen Sie an, scheinbar einfache Fragen zu stellen, sagte er Valentine Kabanets, ein Komplexitätstheoretiker an der Simon Fraser University in Kanada, und „Sie haben keine Ahnung, wohin Sie gehen werden.“

Bekannte Unbekannte

Das P-gegen-NP-Problem verdankt seinen glanzlosen Namen der Angewohnheit von Komplexitätstheoretikern, Rechenprobleme in große Teile zu unterteilen.Komplexitätsklassen” mit Beschriftungen, die an Nasdaq-Tickersymbole erinnern. Ein Rechenproblem ist ein Problem, das im Prinzip durch einen Algorithmus gelöst werden kann – eine genau spezifizierte Liste von Anweisungen. Aber nicht alle Algorithmen sind gleichermaßen nützlich, und die Unterschiede zwischen den Algorithmen weisen auf grundlegende Unterschiede zwischen Problemen in verschiedenen Klassen hin. Die Herausforderung für Komplexitätstheoretiker besteht darin, diese Hinweise in strenge Theoreme über die Beziehungen zwischen Komplexitätsklassen umzuwandeln.

Diese Beziehungen spiegeln unveränderliche Wahrheiten über die Berechnung wider, die weit über eine bestimmte Technologie hinausgehen. „Das ist, als würde man die Gesetze des Universums entdecken“, sagte Kabanets.

„P“ und „NP“ sind die beiden bekanntesten Mitglieder von a wachsende Menagerie von Hunderten von Komplexitätsklassen. Grob gesagt ist P die Klasse von Problemen, die leicht gelöst werden können, beispielsweise die alphabetische Sortierung einer Liste. NP ist die Klasse von Problemen mit leicht überprüfbaren Lösungen, wie z. B. Sudoku-Rätseln. Da alle leicht lösbaren Probleme auch leicht zu überprüfen sind, liegen Probleme in P auch in NP vor. Einige NP-Probleme scheinen jedoch schwer zu lösen – man kann sich die Lösung eines Sudoku-Rätsels nicht sofort vorstellen, ohne vorher viele Möglichkeiten auszuprobieren. Könnte es sein, dass diese scheinbare Härte nur eine Illusion ist – dass es einen einzigen einfachen Trick gibt, um jedes leicht überprüfbare Problem zu lösen?

Wenn ja, dann ist P = NP: Die beiden Klassen sind äquivalent. Wenn das der Fall ist, muss es einen Algorithmus geben, der es trivial macht, riesige Sudoku-Rätsel zu lösen, globale Schifffahrtsrouten zu optimieren, modernste Verschlüsselung zu knacken und den Beweis mathematischer Theoreme zu automatisieren. Wenn P ≠ NP, bleiben viele prinzipiell lösbare Rechenprobleme in der Praxis für immer außerhalb unserer Reichweite.

Lange bevor das P-NP-Problem zum ersten Mal formuliert wurde – und zwar lange vor Beginn der modernen Informatik – machten sich Forscher Sorgen über die Grenzen des formalen mathematischen Denkens. Im Jahr 1921 kämpfte der Mathematiker David Hilbert mit der gleichen Frage, die fast ein Jahrhundert später Carmosinos Aufmerksamkeit erregen sollte, und schlug ein Forschungsprogramm vor, um die Mathematik mit absoluter Sicherheit zu begründen. Er hoffte, von ein paar einfachen Annahmen, den sogenannten Axiomen, ausgehen und eine einheitliche mathematische Theorie ableiten zu können, die drei Schlüsselkriterien erfüllte.

Hilberts erste Bedingung, die Konsistenz, war die wesentliche Voraussetzung dafür, dass die Mathematik frei von Widersprüchen ist: Wenn zwei widersprüchliche Aussagen ausgehend von denselben Axiomen bewiesen werden könnten, wäre die gesamte Theorie unrettbar. Aber eine Theorie könnte widerspruchsfrei und dennoch in ihrer Reichweite begrenzt sein. Das war die Motivation für Hilberts zweite Bedingung, die Vollständigkeit: die Forderung, dass alle mathematischen Aussagen entweder nachweislich wahr oder nachweislich falsch sind. Sein drittes Kriterium, die Entscheidbarkeit, erforderte ein eindeutiges mechanisches Verfahren zur Bestimmung, ob eine mathematische Aussage wahr oder falsch war. Auf einer Konferenz im Jahr 1930 erklärte Hilbert: „Unser Slogan soll sein: ‚Wir müssen es wissen, wir werden es wissen‘.“

Nur ein Jahr später versetzte Gödel Hilberts Traum den ersten Schlag. Er erwies sich dass eine selbstzerstörerische Aussage wie „Diese Aussage ist unbeweisbar“ aus jedem geeigneten Satz von Axiomen abgeleitet werden könnte. Wenn eine solche Aussage tatsächlich nicht beweisbar ist, ist die Theorie unvollständig, wenn sie jedoch beweisbar ist, ist die Theorie inkonsistent – ​​ein noch schlimmeres Ergebnis. In derselben Arbeit bewies Gödel auch, dass keine mathematische Theorie jemals ihre eigene Konsistenz beweisen kann.

Die Forscher hegten immer noch die Hoffnung, dass sich eine zukünftige Theorie der Mathematik, auch wenn sie zwangsläufig unvollständig sei, dennoch als entscheidbar erweisen könnte. Vielleicht könnten sie Verfahren entwickeln, die alle beweisbaren Aussagen identifizieren und gleichzeitig lästige Aussagen wie die von Gödel meiden würden. Das Problem war, dass niemand wusste, wie man diese hypothetischen Verfahren begründet.

Dann, im Jahr 1936, formulierte ein 23-jähriger Doktorand namens Alan Turing Hilberts Entscheidbarkeitsbedingung in der damals noch unbekannten Sprache der Berechnung um und versetzte ihr einen tödlichen Schlag. Turing formulierte ein mathematisches Modell – heute bekannt als Turingmaschine – das alle möglichen Algorithmen darstellen könnte und zeigte, dass Hilberts Verfahren, wenn es existieren würde, in dieses Modell passen würde. Anschließend nutzte er selbstreferenzielle Methoden wie die von Gödel beweisen die Existenz unentscheidbarer Aussagen – oder gleichbedeutend unberechenbarer Probleme, die kein Algorithmus lösen könnte.

Hilberts Programm lag in Trümmern: Es würde für immer grundlegende Grenzen dafür geben, was bewiesen und berechnet werden könnte. Doch als sich Computer von theoretischen Abstraktionen zu realen Maschinen entwickelten, erkannten Forscher, dass Turings einfache Unterscheidung zwischen lösbaren und unlösbaren Problemen viele Fragen unbeantwortet ließ.

In den 1960er Jahren hatten Informatiker schnelle Algorithmen entwickelt, um einige Probleme zu lösen, während für andere die einzigen bekannten Algorithmen unerträglich langsam waren. Was wäre, wenn die Frage nicht nur wäre, ob Probleme lösbar sind, sondern auch, wie schwer sie zu lösen sind?

„Eine reichhaltige Theorie entsteht, und wir kennen die Antworten nicht mehr“, sagte Carmosino.

Abweichende Pfade

Um zu veranschaulichen, wie verwirrend Fragen zur Härte sein können, betrachten wir zwei eng miteinander verbundene Probleme im Zusammenhang mit Diagrammen. Dabei handelt es sich um Netzwerke aus Punkten, sogenannten Knoten, die durch Linien, sogenannte Kanten, verbunden sind. Informatiker nutzen sie, um alles daraus zu modellieren Quantenberechnung zu den Verkehrsfluss.

Angenommen, Sie erhalten einen Graphen und werden gebeten, einen sogenannten Hamilton-Pfad zu finden – eine Route, die jeden Knoten genau einmal durchläuft. Dieses Problem ist im Prinzip klar lösbar: Es gibt nur eine endliche Anzahl möglicher Pfade. Wenn alles andere fehlschlägt, können Sie einfach jeden einzelnen überprüfen. Das ist in Ordnung, wenn es nur wenige Knoten gibt, aber selbst bei geringfügig größeren Diagrammen gerät die Anzahl der Möglichkeiten außer Kontrolle, sodass dieser einfache Algorithmus schnell unbrauchbar wird.

Es gibt ausgefeiltere Hamilton-Pfad-Algorithmen, die einen besseren Kampf bieten, aber die Zeit, die Algorithmen zur Lösung des Problems benötigen, wächst ausnahmslos exponentiell mit der Größe des Diagramms. Diagramme müssen nicht sehr groß sein, bevor selbst die besten Algorithmenforscher herausgefunden haben, dass sie „in angemessener Zeit“ keinen Pfad finden können, sagte er Russel Impagliazzo, ein Komplexitätstheoretiker an der University of California, San Diego. „Und mit ‚angemessene Zeitspanne‘ meine ich ‚bis das Universum untergeht‘.“

Das Hamilton-Pfadproblem hat eine weitere interessante Eigenschaft. Wenn jemand behauptet, auf einem bestimmten Graphen einen Hamilton-Pfad gefunden zu haben, kann er schnell überprüfen, ob die Lösung gültig ist, auch wenn der Graph sehr groß ist. Alles, was Sie tun müssen, ist, dem Pfad zu folgen und die Knoten nacheinander abzuhaken. Dabei müssen Sie sicherstellen, dass Sie keinen Knoten zweimal abgehakt haben. Wenn am Ende keine Knoten fehlen, ist der Pfad hamiltonianisch.

Die zum Ausführen dieses Lösungsprüfungsalgorithmus erforderliche Zeit ist proportional zur Größe des Diagramms. Damit gehört es zur breiteren Kategorie der Polynomalgorithmen, deren Laufzeiten mit zunehmender Polynomfunktion der Diagrammgröße zunehmen. Das Polynomwachstum ist im Vergleich zum exponentiellen Wachstum schwach, sodass Polynomalgorithmen auch bei großen Diagrammen praktikabel bleiben. „Es ist wesentlich effizienter“, sagte Carmosino.

Das Hamilton-Pfadproblem weist eine starke Asymmetrie auf: Sie können eine korrekte Lösung mit einem schnellen Polynomalgorithmus überprüfen, aber um eine Lösung zu finden, benötigen Sie einen langsamen Exponentialalgorithmus. Diese Asymmetrie mag nicht überraschend erscheinen – es ist einfacher, ein künstlerisches Meisterwerk zu erkennen, als eines zu schaffen, einfacher, einen mathematischen Beweis zu überprüfen, als einen neuen Satz zu beweisen –, doch nicht alle Rechenprobleme haben diesen asymmetrischen Charakter. Tatsächlich verhält sich ein Problem, das der Suche nach Hamilton-Pfaden sehr ähnlich ist, ganz anders.

Angenommen, Sie erhalten erneut einen Graphen, müssen nun aber einen „Euleschen Pfad“ finden, der jede Kante genau einmal kreuzt. Auch hier gibt es einen Polynomalgorithmus zur Prüfung möglicher Lösungen, aber dieses Mal gibt es auch einen Polynomalgorithmus zur Lösung des Problems. Hier gibt es keine Asymmetrie. In der Komplexitätstheorie scheinen einige Wege leichter zu finden als andere.

Sowohl das Hamilton-Pfadproblem als auch das Euler-Pfadproblem gehören zur Komplexitätsklasse NP, die so definiert ist, dass sie alle Probleme umfasst, deren Lösungen durch Polynomalgorithmen überprüft werden können. Das Eulersche Pfadproblem fällt ebenfalls in die Klasse P, weil ein Polynomalgorithmus es lösen kann, aber allem Anschein nach gilt das nicht für das Hamiltonsche Pfadproblem. Warum sollten sich diese beiden Graphenprobleme, die oberflächlich so ähnlich sind, so dramatisch unterscheiden? Das ist der Kern des P-NP-Problems.

Universell schwer

Zunächst schienen Komplexitätsklassen praktische Kategorien zum Sortieren ähnlicher, aber nicht direkt zusammenhängender Probleme zu sein – niemand ahnte, dass die Suche nach Hamilton-Pfaden irgendetwas mit anderen schwierigen Rechenproblemen zu tun hatte.

Dann, im Jahr 1971, innerhalb eines Jahres nach seinem Umzug an die University of Toronto, nachdem ihm die Anstellung in den Vereinigten Staaten verweigert worden war, der Komplexitätstheoretiker Stephen Cook veröffentlicht ein außergewöhnliches Ergebnis. Er identifizierte ein bestimmtes NP-Problem mit einer seltsamen Eigenschaft: Wenn es einen Polynomalgorithmus gibt, der dieses Problem lösen kann, kann er auch jedes andere Problem in NP lösen. Cooks „universelles“ Problem schien eine einzelne Spalte zu sein, die die Klasse der scheinbar schwierigen Probleme stützte und sie von den einfachen Problemen darunter trennte. Wenn Sie dieses eine Problem lösen, wird der Rest von NP zusammenbrechen.

Cook vermutete, dass es keinen schnellen Algorithmus für sein universelles Problem gab, und sagte dies mitten im Artikel und fügte hinzu: „Ich bin der Meinung, dass es sich lohnt, erhebliche Anstrengungen zu unternehmen, um diese Vermutung zu beweisen.“ „Erheblicher Aufwand“ wäre eine Untertreibung.

Etwa zur gleichen Zeit wurde ein Doktorand in der Sowjetunion benannt Leonid Lewin bewiesen a ähnliches Ergebnis, außer dass er mehrere verschiedene universelle Probleme identifizierte. Darüber hinaus der amerikanische Komplexitätstheoretiker Richard Karp erwies sich dass die von Cook (und Levin, obwohl Karp und Cook erst Jahre später von Levins Werk wussten) identifizierte Universalitätseigenschaft selbst alles andere als universell war. Nahezu jedes NP-Problem ohne bekannten Polynomalgorithmus – also fast jedes leicht überprüfbare Problem, das schwierig schien – hatte dieselbe Eigenschaft, die als NP-Vollständigkeit bekannt wurde.

Damit sind alle NP-vollständigen Probleme gemeint – das Hamilton-Pfadproblem, Sudoku und Tausende von Anderen – sind in einem präzisen Sinne gleichwertig. „Man hat all diese verschiedenen natürlichen Aufgaben, und auf magische Weise erweisen sie sich alle als dieselbe Aufgabe“, sagte Ilango. „Und wir wissen immer noch nicht, ob diese Aufgabe möglich ist oder nicht.“

Die Lösung der Schwierigkeit eines beliebigen NP-vollständigen Problems würde ausreichen, um die P-gegen-NP-Frage zu lösen. Wenn P ≠ NP, wird die Unterscheidung zwischen einfachen und schweren Problemen durch Tausende von Spalten aufrecht erhalten, die alle gleich stark sind. Wenn P = NP, steht das gesamte Gebäude am Rande des Einsturzes und wartet nur darauf, dass auch nur ein einziges Teil einstürzt.

Cook, Levin und Karp hatten scheinbar viele voneinander unabhängige Probleme vereint. Jetzt mussten die Komplexitätstheoretiker nur noch ein Problem lösen: Ist P = NP oder nicht?

Fünfzig Jahre später bleibt die Frage unbeantwortet. Kabanets verglich das Nachdenken über die Grenzen der Berechnung mit der Vermessung eines riesigen Gebiets ohne jeglichen Sinn für das große Ganze. Ein Wesen mit unbegrenzter Rechenleistung könnte von einem Berggipfel herabblicken und die gesamte Landschaft auf einmal überblicken, doch Normalsterbliche können nicht mit einem solchen Vorteil rechnen. „Diejenigen von uns, die am Fuße des Berges sind, können vielleicht versuchen, auf und ab zu springen, um eine bessere Sicht zu haben“, sagte er.

Angenommen, P = NP. Um dies zu beweisen, müssten Forscher einen schnellen Algorithmus für ein NP-vollständiges Problem finden, das sich möglicherweise in einer dunklen Ecke dieser riesigen Landschaft versteckt. Es gibt keine Garantie, dass sie es bald finden werden: Komplexitätstheoretiker haben es gelegentlich getan entdeckt Geniale Algorithmen für scheinbar schwierige (wenn auch nicht NP-vollständige) Probleme erst nach jahrzehntelanger Arbeit.

Nehmen wir nun an, dass P ≠ NP. Das zu beweisen scheint noch schwieriger zu sein. Komplexitätstheoretiker müssten feststellen, dass es möglicherweise keinen schnellen Algorithmus geben kann, der die besten Bemühungen aller zukünftigen Forscher effektiv vorwegnimmt und vereitelt.

Nicht zu wissen, wo man anfangen soll, ist Teil des Problems. Aber es ist nicht so, dass Forscher es nicht versucht hätten. Im Laufe der Jahrzehnte haben sie das Problem aus vielen Blickwinkeln angegangen und festgestellt, dass ihnen der Weg auf Schritt und Tritt versperrt war. „Das ist eine der offensichtlichsten Wahrheiten in der theoretischen Informatik“, sagte Carmosino. „Wenn man ein Phänomen hat, das so langlebig ist, braucht man eine Erklärung.“

In Carmosinos letztem Studienjahr hatte ihn seine Neugier von Gödel zu einem Aufbaustudiengang in Komplexitätstheorie geführt. Er war überrascht, als er feststellte, dass er mehr Zeit mit Hausaufgaben verbrachte als mit seinem Leidenschaftsprojekt, einem Computerprogramm, das die Erzählstruktur von Märchen lernen und neue Märchen generieren sollte.

„Ich dachte: ‚Wow, ich muss das ernst nehmen‘“, erinnert sich Carmosino. Schon bald war er so in das Thema vertieft, dass sein Mentor ihm sanft vorschlug, seine Pläne für die Zeit nach dem Abschluss noch einmal zu überdenken.

„Er meinte: ‚Wissen Sie, wenn Sie damit weitermachen wollen, wenn Sie weiterhin theoretische Informatik und Komplexitätstheorie betreiben wollen, können Sie das tun: Das nennt sich Graduiertenschule‘“, sagte Carmosino. Nach seinem Masterabschluss zog er 2012 nach San Diego, um bei Impagliazzo an der Promotion zu arbeiten.

Carmosinos Hauptziel bestand zunächst darin, a besser zu verstehen wegweisendes Papier aus zwei Jahrzehnten zuvor, das seine Fantasie beflügelt hatte. Dieses Papier von den Komplexitätstheoretikern Alexander Rasborov und Steven Rüdichhatte gezeigt, dass eine bestimmte „natürliche“ Strategie zum Beweis von P ≠ NP mit ziemlicher Sicherheit scheitern würde, da der Erfolg mit hohen Kosten verbunden wäre – dem völligen Zusammenbruch der Kryptographie –, die Forscher als sehr unwahrscheinlich betrachteten. Forscher interpretierten das Ergebnis von Razborov und Rudich als Hindernis für diesen beliebten Ansatz zum Beweis von P ≠ NP.

Diese „natürliche Beweisbarriere“ ist nur eine von vielen bekannten Barrieren bei der Lösung offener Probleme in der Komplexitätstheorie. Jedes wirkt wie eine Straßensperre und warnt davor, dass ein scheinbar vielversprechender Weg in Wirklichkeit eine Sackgasse ist. Zusammengenommen deuten diese Barrieren darauf hin, dass jeder Beweis, der das P-NP-Problem löst, sich grundlegend von allen in der Vergangenheit verwendeten Beweisen unterscheiden müsste; Deshalb glauben die meisten Forscher, dass eine Lösung noch in weiter Ferne liegt. Aber zumindest weisen Barrieren darauf hin, wo sie nicht suchen sollen.

„Die Komplexitätstheorie ist mit so vielen Hindernissen zugleich verflucht und gesegnet“, sagte Ilango.

Als Carmosino auf die natürliche Beweisbarriere stieß, war es fast 20 Jahre alt. Aber er vermutete, dass daraus für Forscher weitere Lehren gezogen werden konnten. Dieses Gefühl würde sich eines Tages bestätigen, als er und drei Kollegen ein überraschendes Ergebnis bewiesen, indem sie die Barriere der natürlichen Beweise aus der Perspektive der Metakomplexität untersuchten. Ihr Beweis war eines der wenigen wichtigen Ergebnisse, die ein neues Interesse an Metakomplexität weckten und in den letzten Jahren zu rasanten Fortschritten führten.

Aber um den Weg von der natürlichen Beweisbarriere zur Metakomplexität zu verfolgen, müssen wir dorthin zurückkehren, wo wir die Forscher in den 1970er Jahren verlassen haben, als sie begannen, sich mit dem P-NP-Problem auseinanderzusetzen. Was machte es so schwierig, Probleme zu beweisen?

Ein umständlicher Weg

Zunächst versuchten die Forscher zu beweisen, dass P ≠ NP ist – d . Aber sie schnell entdeckt ein Beweis dafür, dass diese Methoden nicht funktionieren würden – das erste große Hindernis bei der Lösung der P-gegen-NP-Frage. Also begannen sie nach einem anderen Ansatz zu suchen und fanden bald einen im Werk von Turings Zeitgenossen Claude Shannon.

Shannon, der in einer Kleinstadt im Norden Michigans aufwuchs, schien keine unwahrscheinliche Persönlichkeit zu sein, die das Informationszeitalter einläuten würde. Dennoch verkörperte er den interdisziplinären Charakter der aufstrebenden Disziplin der Informatik und fühlte sich in der Elektrotechnik und der mathematischen Logik gleichermaßen zu Hause. In seinem MasterarbeitShannon zeigte, wie Schaltkreise aus elektromechanischen Schaltern logische Ausdrücke mit booleschen Variablen darstellen können – Größen, die nur zwei Werte annehmen können (z. B. wahr oder falsch oder 1 und 0).

In diesen Ausdrücken werden boolesche Variablen durch die „Logikgatter“ AND, OR und NOT miteinander verknüpft. Der elementare Ausdruck A AND B zum Beispiel ist wahr, wenn sowohl A als auch B wahr sind, andernfalls ist er falsch; A ODER B hingegen ist wahr, wenn mindestens eine der beiden Variablen wahr ist. Ein NOT-Gatter ist noch einfacher: Es invertiert den Wert einer einzelnen Variablen. Mit genügend dieser Grundbausteine ​​können Sie jede beliebige Berechnung durchführen.

„Wenn Sie am Ende des Tages auf Ihren Computer schauen, was macht er dann? Es läuft auf einem Rundkurs“, sagte Ilango.

Shannons Arbeit schlug einen neuen Weg für Theoretiker vor, über die Schwierigkeit von Rechenproblemen nachzudenken, der als „Schaltkreiskomplexität“ bezeichnet wird, obwohl es sich bei den betreffenden Schaltkreisen lediglich um mathematische Abstraktionen handelt. Eine Zeit lang dachten Forscher, dass dieser Ansatz der Weg sein könnte, P versus NP aufzulösen, aber schließlich stieß die Spur auf die Barriere der natürlichen Beweise.

Das Schaltungskomplexitäts-Framework erfordert ein Überdenken der grundlegendsten Konzepte in Turings Berechnungsmodell. Anstelle von Rechenproblemen und den Algorithmen, die sie lösen, betrachten Forscher hier boolesche Funktionen und die Schaltkreise, die sie berechnen. Eine boolesche Funktion nimmt boolesche Variablen auf – wahr und falsch, Einsen und Nullen – und gibt entweder wahr oder falsch, 1 oder 0 aus. Und wie ein Algorithmus beschreibt eine Schaltung ein Verfahren zum Erzeugen einer Ausgabe bei einer beliebigen Eingabe.

„Ich verstehe, dass die Leute mit der Arbeit an der Schaltungskomplexität begonnen haben, weil sie entschieden haben, dass Turing-Maschinen zu kompliziert sind“, sagte er Ryan Williams, ein Komplexitätstheoretiker am MIT. „Wir können Schaltkreise Gate für Gate untersuchen.“

So wie es viele Algorithmen zur Lösung eines bestimmten Rechenproblems geben kann, einige schneller als andere, können viele verschiedene Schaltkreise jede beliebige boolesche Funktion berechnen, einige mit weniger Gattern als andere. Forscher definieren die Schaltungskomplexität einer Funktion als die Gesamtzahl der Gatter in der kleinsten Schaltung, die sie berechnet. Für eine Funktion mit einer festen Anzahl von Eingangsvariablen ist auch die Schaltungskomplexität eine feste Zahl – bei einigen Funktionen höher als bei anderen.

In vielen Fällen können Sie jedoch kompliziertere Versionen derselben Funktion berücksichtigen, indem Sie die Anzahl der Eingabevariablen erhöhen, genauso wie Sie das Hamilton-Pfadproblem durch die Berücksichtigung größerer Diagramme schwieriger gestalten können. Anschließend beschäftigen sich die Forscher mit der gleichen Frage, die sie auch bei der Untersuchung der Laufzeiten von Algorithmen stellen: Wächst die Mindestanzahl an Gattern, die zur Berechnung einer booleschen Funktion erforderlich sind, polynomisch oder exponentiell, wenn die Anzahl der Eingabevariablen zunimmt? Forscher nennen diese beiden Kategorien von Funktionen „leicht zu berechnen“ bzw. „schwer zu berechnen“.

Eine einfach zu berechnende boolesche Funktion ähnelt einem Rechenproblem der Klasse P – einem Problem, das durch einen Algorithmus gelöst werden kann, der in polynomieller Zeit läuft. Es gibt aber auch analoge Funktionen zu schwierigen NP-Problemen, bei denen die beste von Forschern entdeckte Methode zur Berechnung immer größerer Versionen eine exponentiell steigende Anzahl von Gattern erfordert, die Antwort jedoch leicht überprüft werden kann. Wenn Komplexitätstheoretiker beweisen könnten, dass es tatsächlich keinen besseren Weg zur Berechnung einer solchen Funktion gibt, würde dies bedeuten, dass P ≠ NP.

Dies war die Strategie, die die meisten Komplexitätstheoretiker in den 1980er Jahren verfolgten. Und die Chancen standen auf ihrer Seite. Shannon hatte erwies sich Im Jahr 1949 wurde festgestellt, dass fast jede boolesche Wahrheitstabelle (die lediglich eine lange Liste aller möglichen Ein- und Ausgänge einer booleschen Funktion fester Größe ist) eine Schaltungskomplexität aufweist, die praktisch so hoch wie möglich ist. Er verwendete ein verblüffend einfaches Argument: Es gibt weitaus weniger Möglichkeiten, eine kleine Anzahl von Toren zu kombinieren, als Möglichkeiten, viele Tore zu kombinieren.

„Es gibt einfach nicht genug kleine Rennstrecken“, sagte Aaronson.

Komplexitätstheoretiker befanden sich also in einer merkwürdigen Situation. Wenn fast jede Wahrheitstabelle eine hohe Schaltungskomplexität aufweist, muss fast jede boolesche Funktion schwer zu berechnen sein. Die Forscher mussten lediglich eine einzige solche Funktion identifizieren, von der bekannt war, dass sie ebenfalls zur Klasse NP gehört. Wie schwer könnte das sein?

Crypto Bros

Zunächst ging es schnell voran. 1981 gründeten Sipser und zwei Mitarbeiter erwies sich dass eine bestimmte boolesche Funktion definitiv schwer zu berechnen sei, wenn sie Schaltkreise mit gewissen Einschränkungen bei der Anordnung von Toren verwendeten.

„Die Fantasie bestand darin, dass man in der Lage sein würde, Dinge über diese eingeschränkten Modelle zu beweisen und dann auf dem aufzubauen, was man gelernt hat, um mit immer weniger Einschränkungen zu arbeiten“, sagte Sipser.

1985 machte Razborov den nächsten großen Schritt. Er hatte gerade in Moskau mit dem Graduiertenstudium begonnen und sich zufällig dem Projekt angeschlossen, als er ein Problem in einem anderen Teilgebiet der Mathematik bearbeitete, bei dem sich herausstellte, dass die Lösung des P-NP-Problems eine Voraussetzung dafür war.

„Ich hatte einfach Glück, dass ich nicht wusste, wie schwierig dieses Problem war“, sagte Razborov. „Sonst hätte ich vielleicht gar nicht erst angefangen.“

Razborov analysierte Schaltkreise, die nur UND- und ODER-Gatter enthielten, und erwies sich dass eine bestimmte Funktion mit solchen Schaltkreisen schwer zu berechnen war, egal wie die Gatter angeordnet waren – außerdem war bekannt, dass diese Funktion NP-vollständig war. Alles, was die Forscher tun mussten, um P versus NP aufzulösen, war, Razborovs Techniken auf Schaltkreise mit NICHT-Gattern auszudehnen.

„Es herrschte eine Art allgemeines Gefühl, dass wir es schaffen würden, noch einen Schritt, noch einen Schlag“, sagte Razborov. Aber das ist nicht passiert. Razborov selbst bewies, dass seine Methode scheitern würde, wenn KEINE Tore zum Spiel hinzugefügt würden, und niemand einen anderen Weg nach vorne finden konnte. Im Laufe der Jahre begann er sich zu fragen, warum die Spur versiegt war.

In den Vereinigten Staaten beschäftigte sich Rudich mit der gleichen Frage. Er und Impagliazzo waren College-Klassenkameraden, die gemeinsam ihr Studium abgeschlossen hatten. Ihre Freundschaft war durch eine gemeinsame Faszination für Gödels und Turings selbstreferenzielle Beweise und ihre Auswirkungen auf die Grundlagen der Mathematik und Informatik entstanden.

„Unser Witz war, dass wir einen Knopf mit der Aufschrift „Selbstreferenz“ bekommen würden“, sagte Impagliazzo.

Als Doktoranden arbeiteten sowohl Rudich als auch Impagliazzo an den komplexitätstheoretischen Grundlagen der Kryptographie, einem Fach, das vielleicht die beste praktische Motivation für den Versuch bietet, P ≠ NP zu beweisen. Kryptographen verbergen geheime Nachrichten, indem sie sie in „Pseudozufälligkeit“ hüllen – eine auf diese Weise verschlüsselte Nachricht sieht für jeden Lauscher wie ein zufälliges Durcheinander von Zahlen aus, kann aber vom beabsichtigten Empfänger dennoch entschlüsselt werden. Aber wie können Sie sicher sein, dass es für einen potenziellen Abhörer zu schwierig sein wird, den Code zu knacken?

Hier kommt die Komplexitätstheorie ins Spiel. Die heute am weitesten verbreiteten Verschlüsselungsmethoden basieren alle auf scheinbar schwierigen NP-Problemen – um die Nachricht zu entschlüsseln, bräuchte ein Angreifer einen noch unentdeckten schnellen Algorithmus zur Lösung des Problems. Um nachzuweisen, dass diese Methoden wirklich sicher sind, müssen Sie unter anderem beweisen, dass P ≠ NP. Ohne einen Beweis könne man, so Sipser, nur „hoffen, dass derjenige, vor dem man das Geheimnis verbergen will, kein besserer Mathematiker ist als man selbst.“

Obwohl die Kryptographie an sich schon faszinierend war, schien sie weit von den selbstreferenziellen Argumenten entfernt zu sein, die Rudich und Impagliazzo zuerst auf dieses Gebiet gebracht hatten. Doch als Rudich Schwierigkeiten hatte zu verstehen, warum der Ansatz der Schaltungskomplexität ins Stocken geraten war, wurde ihm klar, dass die beiden Themen gar nicht so weit voneinander entfernt waren. Die Strategie, die die Forscher bei ihren Versuchen, P ≠ NP zu beweisen, gewählt hatten, hatte einen selbstzerstörerischen Charakter, der an Gödels berühmten Satz „Diese Aussage ist unbeweisbar“ erinnerte – und Kryptographie könnte helfen, den Grund dafür zu erklären. In Russland entdeckte Razborov etwa zur gleichen Zeit einen ähnlichen Zusammenhang. Dies waren die Keime der natürlichen Beweisbarriere.

Die Spannung im Kern der natürlichen Beweisbarriere besteht darin, dass die Aufgabe, Funktionen mit hoher Komplexität von Funktionen mit niedriger Komplexität zu unterscheiden, der Aufgabe ähnelt, echte Zufälligkeit von der Pseudozufälligkeit zu unterscheiden, die zum Verschlüsseln von Nachrichten verwendet wird. Wir möchten zeigen, dass sich Funktionen hoher Komplexität kategorisch von Funktionen niedriger Komplexität unterscheiden, um zu beweisen, dass P ≠ NP ist. Aber wir möchten auch, dass Pseudozufälligkeit nicht von Zufälligkeit zu unterscheiden ist, um Vertrauen in die Sicherheit der Kryptographie zu haben. Vielleicht können wir nicht beides haben.

Ein grausamer Witz

Im Jahr 1994 stellten Razborov und Rudich fest, dass sie auf ähnliche Erkenntnisse gestoßen waren, und begannen, zusammenzuarbeiten, um ihre Ergebnisse zu kombinieren. Sie stellten zunächst fest, dass alle früheren Versuche, P ≠ NP mithilfe der Schaltungskomplexität zu beweisen, derselben allgemeinen Strategie gefolgt waren: Identifizieren Sie eine spezielle Eigenschaft einer NP-vollständigen booleschen Funktion und beweisen Sie dann, dass möglicherweise keine einfach zu berechnende Funktion diese Eigenschaft teilen kann. Das würde zeigen, dass die gewählte NP-vollständige Funktion wirklich schwer zu berechnen war, und beweisen, dass P ≠ NP.

Sipser, Razborov und andere hatten dieselbe Strategie erfolgreich verwendet, um ihre begrenzteren Ergebnisse zu beweisen, und in jedem Fall wurde die von den Forschern identifizierte besondere Eigenschaft von den meisten booleschen Funktionen geteilt. Razborov und Rudich prägten den Begriff „natürlicher Beweis“, um sich auf diesen Fall zu beziehen, in dem das Eigentum weit verbreitet war, einfach weil es keine bekannte Alternative gab. Wenn „unnatürliche“ Beweise möglich wären, müssten sie sehr kontraintuitiv sein und diesen Namen verdienen.

Anschließend bewiesen Razborov und Rudich ihr Hauptergebnis: Ein natürlicher Beweis von P ≠ NP würde ein sehr umfassendes Verständnis dafür erfordern, wie sich leicht zu berechnende und schwer zu berechnende Funktionen unterscheiden, und dieses Wissen könnte auch einen schnellen Algorithmus zum einfachen Erkennen antreiben -zu-berechnende Funktionen, auch wenn sie oberflächlich betrachtet kompliziert sind. Wäre den Komplexitätstheoretikern ein natürlicher Beweis für P ≠ NP gelungen, hätten sie eine nahezu unfehlbare Möglichkeit entdeckt, einen Blick auf eine beliebige Wahrheitstabelle zu werfen und festzustellen, ob die entsprechende Funktion eine hohe oder niedrige Schaltungskomplexität aufweist – ein viel stärkeres und allgemeineres Ergebnis als Sie hatten sich vorgenommen, es zu beweisen.

„Man kann fast nicht anders, als mehr zu bekommen, als man erwartet hatte“, sagte Carmosino.

Es ist, als würde man versuchen, eine bestimmte Aussage auf Fakten zu überprüfen, aber jeder Versuch wird zu einer Blaupause für einen Allzweck-Lügendetektor – es scheint zu schön, um wahr zu sein. Für Komplexitätstheoretiker ließ die überraschende Kraft natürlicher Beweise den Erfolg ebenfalls unwahrscheinlicher erscheinen. Wäre ein solcher Beweis jedoch gelungen, wären die unerwarteten Konsequenzen aufgrund des Zusammenhangs zwischen Schaltungskomplexität und Pseudozufälligkeit eine schlechte Nachricht für die Kryptographie.

Um diesen Zusammenhang zu verstehen, stellen Sie sich vor, Sie betrachten die Ausgabespalte in der Wahrheitstabelle einer booleschen Funktion mit vielen Eingabevariablen und ersetzen jedes „wahr“ durch 1 und jedes „falsch“ durch 0:

Wenn die boolesche Funktion eine hohe Schaltungskomplexität aufweist, ist diese lange Liste von Ausgängen im Prinzip nicht von einer wirklich zufälligen Folge von Nullen und Einsen zu unterscheiden – beispielsweise eine Folge, die durch wiederholtes Werfen einer Münze entsteht. Wenn die Funktion jedoch eine geringe Schaltungskomplexität aufweist, muss die Zeichenfolge eine einfache, prägnante Beschreibung haben, auch wenn sie kompliziert aussieht. Das macht es den in der Kryptographie verwendeten pseudozufälligen Zeichenfolgen sehr ähnlich, deren prägnante Beschreibung die geheime Botschaft ist, die in dieser scheinbaren Zufälligkeit verborgen ist.

Das Ergebnis von Razborov und Rudich zeigte also, dass jeder natürliche Beweis von P ≠ NP auch einen schnellen Algorithmus liefern würde, der pseudozufällige Zeichenfolgen mit versteckten Nachrichten von wirklich zufälligen Zeichenfolgen unterscheiden könnte. Eine sichere Kryptographie wäre unmöglich – genau das Gegenteil von dem, was Forscher durch den Nachweis von P ≠ NP beweisen wollten.

Wenn andererseits sichere Kryptografie möglich ist, dann sind natürliche Beweise keine praktikable Strategie zum Nachweis von P ≠ NP – einer Voraussetzung für sichere Kryptografie. Das ist kurz gesagt die natürliche Beweisbarriere. Es schien, als wären die Komplexitätstheoretiker Opfer eines grausamen Scherzes.

„Wenn Sie an Härte glauben, dann sollten Sie glauben, dass es schwierig ist, Härte zu beweisen“, sagte Kabanets.

In die Metaverse

Dieser Zusammenhang zwischen den Implikationen der P ≠ NP-Vermutung und der Schwierigkeit, sie zu beweisen, war faszinierend, aber schwierig zu bestimmen. Zum einen blockierte die Barriere der natürlichen Beweise nur einen Ansatz zum Beweis von P ≠ NP. Zum anderen verband es die Schwierigkeit, P ≠ NP zu beweisen, nicht mit P ≠ NP selbst, sondern mit der Existenz sicherer Kryptographie – ein eng verwandtes, aber nicht ganz gleichwertiges Problem. Um den Zusammenhang wirklich zu verstehen, müssten sich Forscher mit der Metakomplexität vertraut machen.

„Es gibt diese Intuition: ‚Oh, weil P ≠ NP ist, ist es schwierig zu beweisen, dass P ≠ NP‘“, sagte Williams. „Aber um dieser Intuition überhaupt einen Sinn zu geben, muss man anfangen, über die Aufgabe nachzudenken, so etwas wie P ≠ NP als Rechenproblem zu beweisen.“

Das hat Kabanets als Doktorand getan. Er war in der Ukraine aufgewachsen und schloss sein Informatikstudium zwei Jahre nach dem Fall der Sowjetunion ab. In den darauffolgenden Wirren hatte er kaum Gelegenheit, sich den theoretischen Themen zu widmen, die ihn am meisten interessierten.

„Ich wollte etwas akademischeres machen“, erinnert sich Kabanets. „Und ich war auch neugierig, die Welt zu sehen.“ Er zog für sein Graduiertenstudium nach Kanada und lernte dort die natürliche Beweisbarriere kennen. Wie Carmosino war auch Kabanets von dem Ergebnis begeistert. „Es schien sehr tiefgreifend, dass Sie diese Verbindung haben“, sagte er.

Im Jahr 2000, gegen Ende seines Studiums, stellte er fest, dass in seinen Gesprächen mit ihm immer wieder die Barriere der natürlichen Beweise auftauchte Jin Yi Cai, ein Komplexitätstheoretiker, der zu dieser Zeit Toronto im Rahmen eines Sabbaticals besuchte. Sie begannen, die Barriere nicht als Hindernis, sondern als Einladung zu betrachten – eine Gelegenheit, genau zu untersuchen, wie schwierig es war, Probleme als schwierig zu erweisen. Der Krepppapier in dem sie diese neue Perspektive darlegten, sollte eines der einflussreichsten frühen Werke im entstehenden Bereich der Metakomplexität werden.

In der Arbeit von Kabanets und Cai wurde ein Rechenproblem hervorgehoben, das in Razborovs und Rudichs Formulierung der natürlichen Beweisbarriere impliziert ist: Bestimmen Sie anhand der Wahrheitstabelle einer Booleschen Funktion, ob sie eine hohe oder niedrige Schaltungskomplexität aufweist. Sie nannten dies das Minimum Circuit Size Problem oder MCSP.

MCSP ist ein typisches Metakomplexitätsproblem: ein Rechenproblem, dessen Gegenstand nicht die Graphentheorie oder ein anderes externes Thema ist, sondern die Komplexitätstheorie selbst. In der Tat ist es wie eine quantitative Version der Frage, die Komplexitätstheoretiker in den 1980er Jahren dazu veranlasste, P versus NP mithilfe des Schaltungskomplexitätsansatzes anzugehen: Welche booleschen Funktionen sind schwer zu berechnen und welche einfach?

„Wenn wir einen MCSP-Algorithmus entwickeln würden, wäre das eine Möglichkeit, unsere Arbeit in der Komplexitätstheorie zu automatisieren“, sagte Impagliazzo. „Es sollte uns zumindest einen enormen Einblick geben, wie wir unsere Arbeit besser machen können.“

Komplexitätstheoretiker befürchten nicht, dass dieser magische Algorithmus sie arbeitslos machen könnte – sie glauben nicht, dass er überhaupt existiert, denn Razborov und Rudich haben gezeigt, dass ein solcher Algorithmus zur Unterscheidung hochkomplexer Wahrheitstabellen von niedrigkomplexen Wahrheitstabellen Kryptographie ermöglichen würde unmöglich. Das bedeutet, dass MCSP wahrscheinlich ein schwieriges Rechenproblem ist. Aber wie schwer ist es? Ist es NP-vollständig, wie das Hamilton-Pfadproblem und fast jedes andere Problem, mit dem Forscher in den 1960er Jahren zu kämpfen hatten?

Bei Problemen in NP: „Wie schwer ist es?“ ist normalerweise leicht zu beantworten, aber MCSP schien ein seltsamer Ausreißer zu sein. „Wir haben nur sehr wenige ‚umherschwebende‘ Probleme, die nicht mit dieser Insel der NP-vollständigen Probleme in Verbindung stehen, auch wenn sie schwierig zu sein scheinen“, sagte Kabanets.

Kabanets wusste, dass er und Cai nicht die ersten waren, die über das Problem nachdachten, das sie MCSP genannt hatten. Sowjetische Mathematiker untersuchten ab den 1950er Jahren ein sehr ähnliches Problem und versuchten damit, die intrinsische Schwierigkeit verschiedener Rechenprobleme zu verstehen. Leonid Levin hatte damit gerungen, als er Ende der 1960er Jahre die Theorie der NP-Vollständigkeit entwickelte, aber er konnte nicht beweisen, dass sie NP-vollständig war, und veröffentlichte seine bahnbrechende Arbeit ohne sie.

Danach erregte das Problem 30 Jahre lang wenig Aufmerksamkeit, bis Kabanets und Cai seinen Zusammenhang mit der Barriere der natürlichen Beweise feststellten. Kabanets hatte nicht damit gerechnet, die Frage selbst zu klären – stattdessen wollte er erforschen, warum es so schwierig war zu beweisen, dass dieses scheinbar schwierige Problem der Rechenhärte tatsächlich schwierig war.

„Es ist gewissermaßen Meta-Meta-Komplexität“, sagte er Raul Santhanam, ein Komplexitätstheoretiker an der Universität Oxford.

Aber war die Härte bis zum Ende reichte, oder gab es zumindest eine Möglichkeit zu verstehen, warum es den Forschern nicht gelungen war, zu beweisen, dass MCSP NP-vollständig war? Kabanets entdeckte, dass es dafür einen Grund gab: Die Schwierigkeit, die Komplexität von Schaltkreisen zu verstehen, wirkt wie ein Hindernis für jede bekannte Strategie zum Nachweis der NP-Vollständigkeit von MCSP – ein Problem, bei dem es um die Schwierigkeit geht, die Komplexität von Schaltkreisen zu verstehen. Die verdrehte, selbstzerstörerische Logik der natürlichen Beweisbarriere schien unausweichlich.

Es ist auch möglich, dass MCSP nicht NP-vollständig ist, aber auch das erscheint unwahrscheinlich – bestimmte einfachere Varianten des Problems sind bereits als NP-vollständig bekannt.

„Wir haben einfach keinen schönen Ort, um es zu formulieren, der es direkt mit all den anderen Problemen in Verbindung bringt, die wir untersuchen“, sagte Impagliazzo.

Kabanets hatte das seltsame Verhalten von MCSP beleuchtet, wusste aber nicht, wie er weiter vorankommen sollte. Die Metakomplexitätsforschung verlangsamte sich auf ein Minimum. 16 Jahre später blühte es wieder auf, als Forscher einen überraschenden Zusammenhang mit einer anderen grundlegenden Frage entdeckten: Wie schwer ist es, Probleme zu lösen, wenn man sich die meiste Zeit nur darum kümmert, die richtige Antwort zu bekommen?

Krieg der Welten

Bei alltäglichen Problemen sind Antworten, die meistens funktionieren, oft gut genug. Wir planen unsere Pendelfahrten beispielsweise unter Berücksichtigung typischer Verkehrsmuster, nicht unter Berücksichtigung von Worst-Case-Szenarien.

Die meisten Komplexitätstheoretiker sind schwerer zu befriedigen: Sie geben sich nur dann damit zufrieden, ein Problem für einfach zu erklären, wenn sie einen schnellen Algorithmus finden können, der auf jede mögliche Eingabe die richtige Antwort liefert. Dieser Standardansatz klassifiziert Probleme nach dem, was Forscher als „Worst-Case“-Komplexität bezeichnen. Es gibt aber auch eine Theorie der „Durchschnittsfall“-Komplexität, bei der Probleme als einfach gelten, wenn es einen schnellen Algorithmus gibt, der bei den meisten Eingaben die richtige Antwort liefert.

Die Unterscheidung ist für Kryptographen wichtig. Stellen Sie sich ein Rechenproblem vor, das für nahezu jede Eingabe leicht zu lösen ist, mit Ausnahme einiger hartnäckiger Fälle, in denen der beste Algorithmus versagt. Die Worst-Case-Komplexitätstheorie betrachtet dies als ein schwieriges Problem, doch für die Kryptographie ist es nutzlos: Wenn nur einige Ihrer Nachrichten schwer zu entschlüsseln sind, welchen Sinn hat es dann?

Tatsächlich war es Levin, der ein Jahrzehnt nach seiner bahnbrechenden Arbeit zur NP-Vollständigkeit die gründliche Untersuchung der durchschnittlichen Fallkomplexität initiierte. In den Jahren dazwischen war er mit den sowjetischen Behörden in Konflikt geraten – er war ein respektloser Unruhestifter, der gelegentlich die patriotischen Aktivitäten in seiner Jugendgruppe der Kommunistischen Partei untergrub. 1972 wurde ihm aus explizit politischen Gründen die Promotion verweigert.

„Um als junger Forscher in der Sowjetunion erfolgreich zu sein, konnte man nicht sehr eigensinnig sein, und es ist schwer vorstellbar, dass Leonid nicht eigensinnig war“, sagte Impagliazzo.

Levin wanderte 1978 in die Vereinigten Staaten aus und widmete sich Mitte der 1980er Jahre der Komplexität durchschnittlicher Fälle. Er begann mit anderen zusammenzuarbeiten, um die Theorie weiterzuentwickeln, darunter auch mit Impagliazzo, einem damaligen Doktoranden. Doch selbst als sie Fortschritte machten, stellte Impagliazzo fest, dass Forscher oft aneinander vorbeiredeten. Er wollte alle auf den gleichen Stand bringen, und es half nicht, dass Levins Aufsätze bekanntermaßen prägnant waren – derjenige, der initiierte das Feld von durchschnittlicher Fallkomplexität war weniger als zwei Seiten lang.

„Ich wollte Leonids Werk in verständlichere Fachbegriffe übersetzen“, sagte Impagliazzo. Er beschloss, mit einem kurzen, spielerischen Überblick über das Gesamtbild zu beginnen, bevor er sich der Mathematik widmete. „Das hat die Zeitung sozusagen übernommen, und es ist sowieso der einzige Teil, an den sich irgendjemand erinnert.“

Das Krepppapier, 1995 veröffentlicht, wurde sofort zum Klassiker. Impagliazzo prägte skurrile Namen für fünf Welten zeichnen sich durch unterschiedliche Rechenhärtegrade und unterschiedliche kryptografische Fähigkeiten aus. Wir leben in einer dieser Welten, aber wir wissen nicht, welche.

Seit Impagliazzos Artikel erschienen ist, träumen Forscher davon, Teile seines Miniatur-Multiversums zu eliminieren – und damit den Raum der Möglichkeiten einzugrenzen, indem sie beweisen, dass einige der Welten doch nicht möglich sind. Zwei Welten sind besonders verlockende Ziele: solche, in denen Kryptographie unmöglich ist, obwohl P ≠ NP.

In einer dieser Welten, Heuristica genannt, sind alle NP-vollständigen Probleme bei den meisten Eingaben leicht zu lösen, aber schnelle Algorithmen machen gelegentlich Fehler, sodass diese Probleme nach den Maßstäben der Worst-Case-Komplexitätstheorie immer noch als schwierig gelten. Dies ist die Welt, in der Kryptographie unmöglich ist, da fast jeder Code leicht zu knacken ist. In der anderen Welt namens Pessiland ist Kryptographie aus einem anderen Grund unmöglich: Jedes Problem ist im durchschnittlichen Sinne schwierig, aber die Verschlüsselung einer Nachricht macht sie selbst für den beabsichtigten Empfänger unleserlich.

Es stellt sich heraus, dass diese beiden Welten eng mit Metakomplexitätsproblemen verbunden sind – insbesondere ist das Schicksal von Heuristica mit der seit langem bestehenden Frage verbunden, ob MCSP NP-vollständig ist. Die Frage, die Kabanets faszinierte und Levin vor so langer Zeit verblüffte, ist keine bloße Neugier: Es steht eine ganze Welt auf dem Spiel.

Um Heuristica auszuschließen, müssten Forscher die Unterscheidung zwischen Worst-Case- und Average-Case-Komplexität aufheben – das heißt, sie müssten beweisen, dass jeder hypothetische Algorithmus, der ein NP-vollständiges Problem bei den meisten Eingaben korrekt löst, es tatsächlich lösen kann auf alle Fälle. Es ist bekannt, dass diese Art von Verbindung, die als Worst-Case-to-Average-Case-Reduktion bezeichnet wird, für bestimmte Probleme existiert, aber keines davon ist NP-vollständig, sodass diese Ergebnisse nichts Allgemeineres implizieren. Die Abschaffung von Heuristica würde Kryptographen auf halbem Weg zur Verwirklichung des Traums einer sicheren Verschlüsselung bringen, die auf der einzigen Annahme basiert, dass P ≠ NP.

Aber eine Welt zu zerstören ist keine Kleinigkeit. Im Jahr 2003 zwei Komplexitätstheoretiker zeigte dass bestehende Ansätze zum Nachweis von Worst-Case- bis Average-Case-Reduktionen für bekannte NP-vollständige Probleme seltsame Konsequenzen nach sich ziehen würden, was darauf hindeutet, dass solche Beweise wahrscheinlich nicht möglich sind.

Die Forscher müssten einen anderen Ansatz finden und glauben nun, dass MCSP genau das Problem sein könnte, das sie brauchen. Aber das sollte sich erst über ein Jahrzehnt herausstellen. Der erste Blick auf den Zusammenhang ergab sich aus Marco Carmosinos anhaltender Faszination für die natürliche Beweisbarriere.

Carmosino begegnete der Metakomplexitätsforschung zum ersten Mal als Doktorand durch a 2013 Papier von Kabanets und vier anderen Forschern, die den Ansatz zur natürlichen Beweisbarriere weiterentwickelten, den Kabanets mehr als ein Jahrzehnt zuvor entwickelt hatte. Es bestärkte nur seine Überzeugung, dass man aus Razborovs und Rudichs klassischem Aufsatz noch mehr lernen konnte.

„Ich war damals besessen von diesem Papier“, sagte Carmosino. "Nichts hat sich verändert."

Die Besessenheit trug schließlich Früchte, als er einen Semesterworkshop an der University of California in Berkeley besuchte, wo er die meiste Zeit damit verbrachte, mit Impagliazzo, Kabanets und zu sprechen Antonina Kolokolova, ein Komplexitätstheoretiker an der Memorial University of Newfoundland, der mit Kabanets an der Arbeit von 2013 zusammengearbeitet hatte. Carmosino hatte schon einmal mit den dreien zusammengearbeitet, und diese erfolgreiche Zusammenarbeit gab ihm das Selbstvertrauen, sie mit Fragen zu dem Thema zu überschütten, das ihn am meisten faszinierte.

„Er hat die Leute auf eine gute Art und Weise genervt“, erinnerte sich Kabanets.

Zunächst hatte Carmosino neue Ideen zum Beweis der NP-Vollständigkeit für die Version von MCSP, die in Razborovs und Rudichs Aufsatz über die Barriere natürlicher Beweise erschienen war. Aber diese Ideen gingen nicht auf. Stattdessen wurde den vier Forschern durch eine spontane Bemerkung von Impagliazzo klar, dass die natürliche Beweisbarriere leistungsfähigere Algorithmen hervorbringen könnte, als irgendjemand gedacht hatte – in die Straßensperre war eine geheime Karte eingraviert.

In einer 2016 Papierhaben die vier Forscher bewiesen, dass eine bestimmte Art von MCSP-Algorithmus für den Durchschnittsfall verwendet werden kann, um einen Worst-Case-Algorithmus zur Identifizierung von Mustern zu konstruieren, die in zufällig aussehenden Ziffernfolgen verborgen sind – eine Aufgabe, die Informatiker als „Lernen“ bezeichnen. Dies ist ein bemerkenswertes Ergebnis, da das intuitive Lernen schwieriger zu sein scheint als die binäre Klassifizierungsaufgabe – hohe Komplexität oder niedrige Komplexität –, die von einem MCSP-Algorithmus durchgeführt wird. Und überraschenderweise verknüpfte es die Worst-Case-Komplexität einer Aufgabe mit der Durchschnitts-Case-Komplexität der anderen.

„Es war nicht offensichtlich, dass eine solche Verbindung überhaupt bestehen würde“, sagte Impagliazzo.

Ein schneller Algorithmus für MCSP ist für allgemeine Boolesche Schaltkreise rein hypothetisch: Er kann nicht existieren, es sei denn, MCSP erweist sich trotz aller gegenteiligen Beweise als einfaches Rechenproblem, und das bedeutet, dass der in der Arbeit der vier Forscher implizierte Lernalgorithmus dies ist ebenso hypothetisch.

Aber für einige einfachere Versionen von MCSP – die Unterscheidung von Wahrheitstabellen mit hoher Komplexität von Wahrheitstabellen mit niedriger Komplexität, wenn bestimmte Einschränkungen für die Schaltkreise bestehen – sind seit vielen Jahren schnelle Algorithmen bekannt. Die Arbeit von Carmosino, Impagliazzo, Kabanets und Kolokolova zeigte, dass diese Algorithmen in Lernalgorithmen umgewandelt werden könnten, die ebenfalls eingeschränkt, aber dennoch leistungsfähiger sind als alle, die Forscher zuvor auf einem so strengen theoretischen Niveau verstanden hatten.

„Irgendwie ermöglicht ihr selbstreferenzieller Ansatz es, Dinge zu tun, die man mit Standardproblemen scheinbar nicht tun kann“, sagte Ilango.

Das Ergebnis erregte die Aufmerksamkeit von Komplexitätstheoretikern, die an anderen Themen arbeiteten. Es war auch eine Vorschau auf weitere Zusammenhänge zwischen Metakomplexität und durchschnittlicher Fallkomplexität, die in den kommenden Jahren entstehen würden.

Vor allem war es ein Beweis dafür, wie weit Forscher kommen können, wenn sie einfache Fragen zu Hindernissen stellen, die auf den ersten Blick nur ihren Fortschritt zu behindern scheinen.

„Diese Art von Dualität ist in den letzten 30 oder 40 Jahren der Komplexität ein Thema“, sagte Impagliazzo. „Die Hindernisse sind oft die Chancen.“

Teilkredit

Der Fortschritt hat sich in den Jahren, seit Carmosino und seine Kollegen ihre Arbeit veröffentlicht haben, nur beschleunigt.

„Es passieren neue Dinge“, sagte Kolokolova. „Es gibt viele wirklich sehr, sehr kluge Nachwuchsforscher.“

Ilango ist einer dieser jungen Forscher – in seinen ersten drei Jahren an der Graduiertenschule hat er das gewaltige offene Problem des Nachweises der NP-Vollständigkeit von MCSP mit einer zweigleisigen Strategie angegangen: dem Nachweis der NP-Vollständigkeit für einfacher Versionen von MCSP, wie es Schaltungskomplexitätsforscher taten, als sie in den 1980er Jahren P gegen NP angriffen, und gleichzeitig die NP-Vollständigkeit für bewiesen kompliziertere Versionen, die intuitiv schwieriger erscheinen und daher vielleicht einfacher zu beweisen sind.

Ilango führt sein Interesse an Metakomplexität darauf zurück Erich Allender, ein Komplexitätstheoretiker an der Rutgers University und einer der wenigen Forscher, die in den 2000er und frühen 2010er Jahren weiterhin an Metakomplexität arbeiteten. „Seine Begeisterung war ansteckend“, sagte Ilango.

Ein weiterer von Allender inspirierter junger Forscher ist Shuichi Hirahara, jetzt Professor am National Institute of Informatics in Tokio. Noch als Doktorand im Jahr 2018 enthüllte Hirahara das wahre Ausmaß der Beziehung zwischen Metakomplexität und durchschnittlicher Fallkomplexität, die Carmosino und seine Co-Autoren entdeckt hatten. Diese vier Forscher hatten einen Zusammenhang zwischen der durchschnittlichen Komplexität eines Problems – MCSP – und der Worst-Case-Komplexität eines anderen Problems – Boolesches Lernen – gefunden. Hirahara entwickelte seine Techniken weiter ableiten eine Reduzierung vom Worst-Case- auf den Durchschnittsfall für MCSP. Sein Ergebnis impliziert, dass ein hypothetischer Durchschnittsfall-MCSP-Algorithmus wie der, den Carmosino und seine Kollegen in Betracht gezogen hatten, tatsächlich leistungsfähig genug wäre, um eine etwas andere Version von MCSP fehlerfrei zu lösen.

Hiraharas Ergebnis ist spannend, weil viele Forscher vermuten, dass MCSP NP-vollständig ist, im Gegensatz zu allen anderen Problemen, für die Reduktionen vom Worst-Case- zum Average-Case bekannt sind. Wenn sie Hiraharas Ergebnisse so erweitern können, dass sie alle Durchschnittsfallalgorithmen abdecken, und dann beweisen können, dass MCSP NP-vollständig ist, würde das beweisen, dass wir nicht in der Heuristik leben.

„Das wäre wirklich ein weltbewegendes Ergebnis“, sagte Santhanam.

Der Beweis, dass MCSP NP-vollständig ist, scheint eine große Herausforderung zu sein – schließlich ist die Frage seit über 50 Jahren offen. Aber nach einem Durchbruch Letztes Jahr von Hirahara sind Forscher jetzt viel näher dran, als man es vor ein paar Jahren erwartet hätte.

Hirahara bewies die NP-Vollständigkeit für eine Variante des Problems namens partielles MCSP, bei der bestimmte Einträge in jeder Wahrheitstabelle ignoriert werden. Sein Beweis stützte sich auf von Ilango entwickelte Methoden, um zu zeigen, dass partielles MCSP einem scheinbar unabhängigen Problem entspricht, bei dem es sich um eine kryptografische Technik namens „Secret Sharing“ handelt. Dies ist eine Möglichkeit, eine verschlüsselte Nachricht auf viele Personen aufzuteilen, sodass sie nur dann entschlüsselt werden kann, wenn ein bestimmter Teil von ihnen zusammenarbeitet.

Für jede reale Anwendung in der Kryptographie möchten Sie diesen Bruchteil im Voraus wissen, aber mit Hilfe zusätzlicher kryptografischer Tricks können Sie ein frustrierendes Szenario konstruieren, in dem es schwierig ist, einfach herauszufinden, wie viele Personen zusammenarbeiten müssen. Hirahara fand einen Weg, zu beweisen, dass dieses erfundene kryptografische Problem NP-vollständig war, und zeigte dann, dass der Beweis auch die NP-Vollständigkeit von partiellem MCSP impliziert.

Dieses Ergebnis begeisterte Forscher im Bereich der Metakomplexität noch mehr als Hiraharas frühere Arbeit, und auch andere Forscher wurden darauf aufmerksam – der Komplexitätstheoretiker und Blogger Lance Fortnow nannte es das Ergebnis des Jahres. Das liegt daran, dass die Auseinandersetzung mit solchen „Partialfunktionen“-Versionen von Rechenproblemen ein wichtiger Zwischenschritt in anderen Beweisen der NP-Vollständigkeit war.

„Es ist eine erstaunliche Arbeit“, sagte Williams. „Alle dachten, dass diese Teilprobleme ungefähr den gleichen Schwierigkeitsgrad hätten wie das Gesamtproblem.“

Es bestehen weiterhin Hindernisse für den Nachweis der NP-Vollständigkeit für die Vollversion von MCSP. Aber es gibt keine der Art von Hindernissen, die darauf hindeuten, dass ein völlig neues Toolkit erforderlich ist – es kann nur darum gehen, den richtigen Weg zu finden, bekannte Techniken zu kombinieren. Ein Beweis würde endlich den Status eines der wenigen Probleme klären, die sich seit der Existenz der Komplexitätstheorie einer Klassifizierung widersetzt haben. Per E-Mail schrieb Levin: „Es würde mich demütigen, zu zeigen, dass ich dumm war, es nicht sehen zu können :-).“

Die fehlenden Teile

MCSP ist nicht einmal das einzige Metakomplexitätsproblem, das zu einem großen Durchbruch geführt hat. Im Jahr 2020 der Kryptograf von Cornell Tech Rafael Pass und sein Doktorand Yanyi Liu habe einen Zusammenhang entdeckt zwischen einem anderen Metakomplexitätsproblem und einem grundlegenden kryptografischen Protokoll, das die Grenze zwischen Heuristica und Pessiland definiert, der schlimmsten von Impagliazzos Welten (wo NP-vollständige Probleme im durchschnittlichen Sinne schwierig sind, Kryptographie jedoch immer noch unmöglich ist). Das macht das Problem, das sie untersucht haben, zu einem Hauptkandidaten für einen Angriff auf Pessiland und ihre neuere Arbeiten weist darauf hin, dass es auch gegen Heuristica wirken könnte.

„Es fehlen verschiedene Puzzleteile“, sagte Pass. „Für mich ist es einfach magisch, dass diese Bereiche so eng miteinander verbunden sind.“

Hirahara warnt davor, dass Forscher, die die Welten ausmerzen wollen, die Impagliazzo vor 30 Jahren heraufbeschworen hat, immer noch vor Herausforderungen stehen. „Ich würde gerne sagen, dass Heuristica und Pessiland irgendwann ausgeschlossen sein werden, aber ich bin mir nicht sicher, wie nah wir dran sind“, sagte er.

Viele Forscher gehen davon aus, dass die größte Schwierigkeit darin bestehen wird, eine scheinbar harmlose Lücke zwischen zwei verschiedenen Modellen mit durchschnittlicher Fallkomplexität zu schließen. Kryptographen untersuchen in der Regel Durchschnittsalgorithmen, die Fehler in beide Richtungen machen und gelegentlich zufällige Zeichenfolgen fälschlicherweise als pseudozufällig kennzeichnen und umgekehrt. Hiraharas Reduktionen vom Worst-Case- zum Durchschnittsfall funktionieren unterdessen für Durchschnittsfall-Algorithmen, die nur die erste Art von Fehler machen. Subtile Unterscheidungen wie diese können in der Komplexitätstheorie einen großen Unterschied machen. Aber trotz dieser und vieler anderer Hürden kann Allender nicht anders, als vorsichtigen Optimismus auszudrücken.

„Ich versuche, nicht zu sehr davon überzeugt zu sein, denn es gibt eine ziemlich fundierte Erfolgsbilanz, dass nichts funktioniert“, sagte er. „Aber wir sehen viele wirklich aufregende Entwicklungen – Möglichkeiten, Dinge zu überwinden, die wie Barrieren aussahen.“

Wenn es eine Lektion gibt, die Forscher aus ihren Bemühungen, die Frage P versus NP zu beantworten – oder auch nur zu verstehen – gelernt haben, dann ist es, dass die Komplexitätstheorie selbst komplex ist. Aber genau diese Herausforderung macht die Suche so lohnenswert.

„Eigentlich ist es großartig, dass es so schwer ist“, sagte Carmosino. „Ich werde mich nie langweilen.“

Anmerkung des Herausgebers: Scott Aaronson ist Mitglied von Quanta Magazine Beirat.