Das 50 Jahre alte Problem, das sich der theoretischen Informatik entzieht

Eine Lösung für P vs NP könnte unzählige Rechenprobleme lösen – oder sie für immer außer Reichweite halten.



Das Steiner-Baum-Problem: Verbinden Sie eine Menge von Punkten mit Liniensegmenten minimaler Gesamtlänge.

Das Steiner-Baum-Problem: Verbinden Sie eine Menge von Punkten mit Liniensegmenten minimaler Gesamtlänge.Derek Brahney

27. Oktober 2021

eins. Am Montag, dem 19. Juli 2021, mitten in einem weiteren seltsamen Pandemiesommer, twitterte ein führender Informatiker auf dem Gebiet der Komplexitätstheorie eine öffentlich-rechtliche Nachricht über einen Verwaltungsfehler in einer Zeitschrift. Er verabschiedete sich mit einem sehr geladen





wenn es regnen wird

Schönen Montag.

Das EDV-Problem

Diese Geschichte war Teil unserer Ausgabe vom November 2021

  • Siehe den Rest des Problems
  • Abonnieren

In einem Paralleluniversum hätte es tatsächlich ein sehr fröhlicher Montag werden können. Ein Beweis war online in der angesehenen Zeitschrift ACM Transactions on Computational Theory erschienen, die mit herausragender Originalforschung handelt, die die Grenzen machbarer Berechnungen auslotet. Das Ergebnis soll das Problem aller Probleme lösen – der Heilige Gral der theoretischen Informatik, mit einem Preisgeld von 1 Million Dollar und einem Ruhm, der für immer mit dem von Aristoteles konkurriert.



Dieses geschätzte Problem – bekannt als P versus NP – gilt gleichzeitig als das wichtigste in der theoretischen Informatik und Mathematik und ist völlig unerreichbar. Es behandelt Fragen, die für das Versprechen, die Grenzen und die Ambitionen der Berechnung von zentraler Bedeutung sind, und fragt:

Warum sind einige Probleme schwieriger als andere?

Welche Probleme können Computer realistisch lösen?

Wie lange wird es dauern?



Und es ist eine Suche mit großen philosophischen und praktischen Auszahlungen.

Schauen Sie, diese P-gegen-NP-Frage, was soll ich sagen? Scott Aaronson, ein Informatiker an der University of Texas in Austin, schrieb in seinem Erinnerungen an Ideen , Quantencomputing seit Demokrit . Man bezeichnet es gerne als „das wohl zentrale ungelöste Problem der theoretischen Informatik“. Das ist eine komische Untertreibung. P vs NP ist eine der tiefsten Fragen, die sich Menschen jemals gestellt haben.

Man kann sich die Protagonisten dieser Geschichte wie folgt vorstellen:

P steht für Probleme, die ein Computer bequem lösen kann.

NP steht für Probleme, die, sobald sie gelöst sind, leicht zu überprüfen sind – wie Puzzles oder Sudoku. Viele NP-Probleme entsprechen einigen der hartnäckigsten und dringendsten Probleme, mit denen die Gesellschaft konfrontiert ist.

Die Millionen-Dollar-Frage, die sich bei P vs. NP stellt, lautet: Sind diese beiden Klassen von Problemen ein und dasselbe? Das heißt, könnten die scheinbar so schwierigen Probleme tatsächlich mit einem Algorithmus in angemessener Zeit gelöst werden, wenn nur der richtige, teuflisch schnelle Algorithmus gefunden werden könnte? Dann sind viele schwierige Probleme plötzlich lösbar. Und ihre algorithmischen Lösungen könnten gesellschaftliche Veränderungen von utopischem Ausmaß bewirken – in Medizin und Technik und Wirtschaft, Biologie und Ökologie, Neurowissenschaften und Sozialwissenschaften, Industrie, Kunst, sogar Politik und darüber hinaus.

Manchmal entwickeln sich die Klassifikationen weiter – schwierige Probleme erweisen sich als einfach, wenn Forscher effizientere Lösungen finden. Das Testen, ob eine Zahl beispielsweise eine Primzahl ist, ist seit Mitte der 1970er Jahre in der Klasse NP bekannt. Aber im Jahr 2002 entwickelten drei Informatiker am Indian Institute of Technology Kanpur einen bedingungslosen Beweis und einen cleveren Algorithmus, der schließlich bestätigte, dass das Problem auch in P.

Wenn alle die kniffligen Probleme ließen sich mit solchen algorithmischen Tricks transformieren, die Folgen für die Gesellschaft – für die Menschheit und unseren Planeten – wären enorm.

Zunächst einmal würden Verschlüsselungssysteme geknackt, die meist auf NP-Problemen basieren. Wir müssten einen völlig anderen Ansatz zum Senden sicherer Kommunikation finden. Die Proteinfaltung, eine 50 Jahre alte große Herausforderung in der Biologie, würde handhabbarer werden und neu entdeckte Fähigkeiten freisetzen, um Medikamente zu entwickeln, die Krankheiten heilen oder behandeln, und Enzyme zu entdecken, die Industrieabfälle abbauen. Es würde auch bedeuten, optimale Lösungen für alltägliche schwierige Probleme zu finden, wie z. B. die Planung eines Roadtrips, um alle Ziele mit minimalem Fahraufwand zu erreichen, oder die Bestuhlung von Hochzeitsgästen, sodass nur Freunde denselben Esstisch teilen.

Seit dem Beginn des P vs. NP-Problems vor 50 Jahren – entstanden aus der bedeutsamen Schnittmenge von mathematischer Logik und elektronischer Computertechnologie – haben Forscher auf der ganzen Welt herkulische Versuche unternommen, eine Lösung zu finden. Einige Informatiker haben vorgeschlagen, dass die Bemühungen besser mit denen von Sisyphos verglichen werden könnten, der ohne Entschlossenheit arbeitete. Aber während diejenigen, die das Problem zuerst erforscht haben, keine Zeit mehr haben, um eine Lösung zu finden, nehmen die neueren Generationen die Suche gerne auf.

Für Manuel Sabin, einen Informatiker, der gerade seinen PhD an der UC Berkeley abschließt, liegt der Reiz darin, die Unmöglichkeit von Problemen zu untersuchen, bei denen Sie die Antwort nicht kennen, bis die Sonne die Erde verschlingt. Die Suche mag weltfremd sein, aber Sabin würde es bereuen, sich nicht gegen diese Windmühlen gewendet zu haben.

Timothy Gowers, ein Mathematiker an der University of Cambridge, nennt es eine meiner persönlichen mathematischen Krankheiten. Er verlor im Sommer 2013 an der Verfolgung, nachdem er Studenten um einen Aufsatz über das Thema in einem Test gebeten hatte. Wie er in seinem Blog erzählte: Nachdem ich die Aufsätze im Juni bewertet hatte, dachte ich, ich würde einfach ein oder zwei Stunden damit verbringen, noch einmal über das Problem nachzudenken, und aus diesen ein oder zwei Stunden wurden versehentlich ungefähr drei Monate.

Stützen

Das Handlungsreisende-Problem: Finden Sie die kürzestmögliche Route, die jede Stadt einmal besucht und schließlich zurück zur Herkunftsstadt führt.

DEREK BRAHNEY

Die Suche hat sogar den Informatiker Stephen Cook von der University of Toronto ins Wanken gebracht, der das Problem formulierte und 1971 mit einer bahnbrechenden Arbeit das Gebiet der Rechenkomplexität ins Leben rief. Für diese Arbeit gewann er den Turing Award, das Äquivalent der Informatik zum Nobelpreis. Aber er hatte kein Glück, eine Lösung zu finden. Cook sagt, er hatte nie gute Ideen – es ist einfach zu schwierig.

zwei. Michael Sipser, Informatiker am MIT, schätzt, dass er insgesamt bis zu einem Jahrzehnt an dem Problem gearbeitet hat. Während der Graduiertenschule in den 1970er Jahren interessierte er sich dafür und wettete mit seinem Kommilitonen Len Adleman um eine Unze Gold, dass es bis zum Ende des Jahrhunderts gelöst sein würde (Sipser zahlte).

In den 1980er Jahren erzielte er ein schönes Ergebnis, indem er eine Version des Problems mit einem eingeschränkten Rechenmodell löste – was zu einer aufregenden Zeit auf dem Gebiet mit mehreren schönen Ergebnissen führte, die Anlass zur Hoffnung gab, dass eine Lösung nicht allzu weit entfernt sein könnte.

Sipser kommt immer noch hin und wieder auf das Problem zurück, und er ist ein standhafter Botschafter, der unzählige Vorträge zu diesem Thema hält.

Er nähert sich einer zugänglichen Erklärung von P vs. NP mit einem grundlegenden Multiplikationsproblem: 7 × 13 = ?

Die Antwort, 91, lässt sich leicht im Kopf berechnen. Obwohl das Multiplizieren größerer Zahlen nicht so einfach ist, würde ein Computer praktisch keine Zeit dafür benötigen.

Aber diese Probleme umzudrehen, ist eine andere Sache. Stellen Sie sich zum Beispiel vor, Sie finden die beiden 97-stelligen Primzahlen, die sich multiplizieren, um diese sehr große Zahl zu erzeugen:

wann beginnt das universelle grundeinkommen

0437213507 5003588856 7930037346 310 7418240490 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Dieses Faktorisierungsproblem war Teil einer Herausforderung, bei der die Schwierigkeit bewertet wurde, die in der Kryptographie verwendeten RSA-Schlüssel zu knacken. Sipser erklärt, dass 80 Prozessoren fünf Monate ununterbrochen rechnen mussten, um es zu lösen – was mit nur einem einzigen Prozessor ungefähr 33 Jahre ausmacht. Factoring ist ein schwieriges Problem, weil alle gängigen Methoden die Antwort mit roher Gewalt suchen und die astronomische Anzahl von Möglichkeiten Stück für Stück prüfen. Selbst für einen Computer ist dies ein langsamer Prozess.

Die interessante Frage hier ist, müssen Sie wirklich suchen? Sagt Sipser. Oder gibt es eine Möglichkeit, das Faktorisierungsproblem zu lösen, die schnell auf die Antwort zoomt, ohne zu suchen? Wir kennen die Antwort auf diese Frage nicht.

Fragen wie diese berühren den Kern der Rechenkomplexität – ein Feld voller scheußlicher Probleme, die Forscher zu verstehen versuchen. Aaronson hat einen Complexity Zoo zusammengestellt, einen Online-Katalog mit 545 Klassen von Problemen (Tendenz steigend). Jedes wird nach seiner Komplexität oder Schwierigkeit und den Ressourcen – Zeit, Gedächtnis, Energie – klassifiziert, die erforderlich sind, um Lösungen zu finden. P und NP sind die Hauptattraktionen.

Wie es der wissenschaftliche Zufall will, kam ein sowjetischer Mathematiker, Leonid Levin, mehr oder weniger zur gleichen Zeit zu einem Ergebnis, das dem von Cook entsprach.

P ist die Klasse, mit der alles begann. Es ist die Klasse von Problemen, die von einem Computer in angemessener Zeit gelöst werden können. Genauer gesagt sind P-Probleme solche, bei denen die Zeit, die zum Finden einer Lösung benötigt wird, durch eine Polynomfunktion beschrieben werden kann, wie z n ^2. In Polynomzeitalgorithmen gilt: n ist die Größe der Eingabe, und das Wachstum gegenüber dieser Eingabe erfolgt mit einer angemessenen Rate (in diesem Fall mit der Zweierpotenz).

Im Gegensatz dazu sind einige schwierige NP-Probleme möglicherweise nur durch Algorithmen lösbar, deren Laufzeiten durch eine Exponentialfunktion definiert sind, wie z. B. 2^n, was eine exponentielle Wachstumsrate erzeugt (wie bei der Ausbreitung von Covid). NP, wie Aaronson es beschreibt, ist die Klasse der zerstörten Hoffnungen und müßigen Träume. Er klärt jedoch schnell ein häufiges Missverständnis auf: Nicht alle NP-Probleme sind schwierig. Die Klasse NP enthält tatsächlich die Klasse P – denn Probleme mit einfachen Lösungen sind natürlich auch leicht zu überprüfen.

Die anspruchsvolleren Probleme von NP haben oft bedeutsame praktische Anwendungen. Für diese Probleme würde eine erschöpfende Brute-Force-Suche nach einer Lösung wahrscheinlich unpraktisch lange dauern – geologische Zeit – bevor sie eine Antwort liefert. Wenn ein Brute-Force-Suchalgorithmus der bestmögliche Algorithmus ist, dann ist P nicht gleich NP.

Und unter den Kennern ist das offenbar der Konsens, den manche eher mit religiösem Glauben vergleichen: P ≠ NP. Die meisten lassen nur einen Hoffnungsschimmer zu, dass sich das Gegenteil bewahrheiten wird. Ich würde ihm eine Chance von 2 bis 3 % geben, dass P gleich NP ist, sagt Aaronson. Das sind die Wettquoten, die ich nehmen würde.

Das im Juli veröffentlichte Ergebnis lieferte einen Beweis für genau diesen Weitschuss. Aber es war nur das Neueste in einer langen Tradition von Beweisen, die nicht durchhalten. Innerhalb eines Tages nach der Veröffentlichung wurde das Papier in einer Wendung von Ereignissen, die Monty Python würdig waren, aus dem Online-Journal entfernt; dann schien es kurz wieder aufzutauchen, bevor es endgültig verschwand. Es war die neueste Version eines Papiers, das der Autor in den letzten zehn Jahren mehr als 60 Mal auf dem arXiv-Preprint-Server veröffentlicht hatte. Der Chefredakteur der Zeitschrift erklärte auf Twitter, dass das Ergebnis abgelehnt worden sei, aber in einem Fall von menschlichem Versagen habe sich die Disposition des Papiers irgendwie von Ablehnung zu Annahme geändert und der Beweis seinen Weg zur Veröffentlichung gefunden.

3. Als ich Anfang August Steve Cook in seinem Büro auf dem Campus traf, hatte er diesen neuesten P vs. NP-Proof-Snafu weder gesehen noch gehört. Der 81-Jährige war erst kürzlich in den Ruhestand getreten, da sein Gedächtnis nachließ. Deshalb haben wir James hier, sagte er – sein Sohn James, 36, ebenfalls Informatiker, war bei meinem Besuch dabei. Steve war gerade dabei, sein Büro auszuräumen. Ein riesiger Papierkorb stand in der Mitte des Raums und füllte sich mit alten, vergilbten Ausgaben des Journal of Symbolic Logic, daneben wartete ein Stapel superfetter Telefonbücher aus Toronto.

Im Laufe der Jahre hat Cook viele Beweise gesehen, die vorgeben, das P vs. NP-Problem zu lösen. Im Jahr 2000, nachdem das Clay Mathematics Institute es zu einem der sieben ungelösten Millenniumsprobleme ernannt hatte (jeweils mit einem Preisgeld von 1 Million US-Dollar), wurde er mit Nachrichten von Menschen überschwemmt, die dachten, sie hätten triumphiert. Alle Ergebnisse waren falsch, wenn nicht sogar schlicht falsch. Etwa die Hälfte behauptete, bewiesen zu haben, dass P gleich NP ist; die andere Hälfte ging in die entgegengesetzte Richtung. Vor nicht allzu langer Zeit behauptete eine Person, beides bewiesen zu haben.

Cook vermutete in seiner Arbeit von 1971, dass P nicht gleich NP ist (er formulierte es mit einer anderen damals üblichen Terminologie). Seitdem hat er eine beträchtliche, wenn auch unbestimmte Zeit investiert, um festzustellen, dass dies der Fall ist. Ich habe keine gute Erinnerung an die Arbeit, sagt er, aber seine Kollegen erinnern sich, dass Steve immer, wenn sie am Wochenende in die Abteilung kamen, in seinem Büro war.

Wenn er nicht gerade Segelboote fährt, ist Cook niemand, der es eilig hat; Er gibt einer Idee gerne Zeit. Und seine ehemaligen Schüler erinnern sich an einen deutlichen Mangel an Prahlerei. Die Informatikerin Anna Lubiw von der University of Waterloo sagt, dass er, als er Cooks Theorem – Teil dieser bahnbrechenden Arbeit – lehrte, es nie als solches bezeichnete und nicht einmal einen Hinweis darauf gab, dass er die Person war, die es bewiesen hatte. Maria Klawe, Mathematikerin und Informatikerin und Präsidentin des Harvey Mudd College, sagt, sie habe Cook regelmäßig korrigiert, wenn er sich verirrte, indem er Beweise lehrte, die er in- und auswendig kannte: Er blieb stecken und sagte: „Okay. Sagen Sie mir, wie der Beweis ausgeht.“ Cook war auch bekannt für seine Bescheidenheit in Bezug auf Förderanträge und Berichte über seine Forschung – er würde gestehen: Ehrlich gesagt, ich habe wenig Fortschritte gemacht …

Die Evolution der Informatik Die Berechnung der Energieniveaus eines Heliumatoms war 1958 deutlich schwieriger als heute. Aber ein Vergleich der Methoden von damals und heute offenbart einige kontraintuitive Anomalien über den Einfluss der Informatik.

Er machte jedoch Fortschritte bei der Rekrutierung von James, um sich der Sache anzunehmen. Schon früh zeigte James Interesse an Mathematik und Informatik – im Alter von neun Jahren drängte er seinen Vater, ihm Boolesche Algebra und Logik beizubringen. Vor ein paar Jahren, nachdem er in Berkeley promoviert und bei Google gearbeitet hatte, machte er sich als unabhängiger Forscher auf den Weg, um sich auf verschiedene Projekte zu konzentrieren, von denen einige indirekt mit P vs. NP in Verbindung stehen. Und trotz der Erfolgsbilanz ist James, der seinem Vater auffallend ähnlich sieht, unerschrocken, solch eine scheinbar endlose Suche geerbt zu haben. Er betrachtet es wie jedes mathematische Unterfangen: Es ist ein lustiges Puzzle. Auf diese Fragen muss es eine Antwort geben, sagt er. Und es ist wie, komm schon, jemand muss es lösen. Lassen Sie uns das einfach herausfinden. Es ist lange her. Es ist peinlich, dass wir die Antwort noch nicht kennen.

Der Mangel an Fortschritt hat diese Gemeinschaft glücklicher Sisyphusaner nicht davon abgehalten, das 50-jährige Jubiläum der Rechenkomplexität zu feiern. Die Feierlichkeiten begannen 2019, als sich Anhänger aus der ganzen Welt am Fields Institute for Research in Mathematical Sciences der University of Toronto zu einem Symposium zu Cooks Ehren versammelten. Christos Papadimitriou, ein Informatiker an der Columbia University, der einen Großteil seiner Karriere mit der Arbeit an P vs. NP verbracht hat, eröffnete die Veranstaltung mit einem öffentlichen Vortrag, in dem er nicht ein halbes Jahrhundert, sondern Jahrtausende zurückblickte.

Er begann mit der Beschreibung uralter Suche nach Lösungen – mit algebraischen Werkzeugen oder Lineal und Kompass, die er als rudimentäre Formen der Berechnung betrachtete. Papadimitrious Geschichte gelangte schließlich zu Alan Turing, dem britischen Mathematiker, dessen 1936 erschienener Artikel On Computable Numbers die Begriffe Algorithmus und Berechnung formalisierte. Turing zeigte auch – mit seiner Idee einer universellen Rechenmaschine –, dass es keinen mechanischen Weg gibt (d. h. von einer Maschine durchgeführt), um die Wahrheit oder Falschheit mathematischer Aussagen zu beweisen; kein systematischer Weg, das Beweisbare vom Unbeweisbaren zu unterscheiden.

Papadimitriou sagte, er betrachte Turings Aufsatz als die Geburtsurkunde der Informatik – und die Geburtsurkunde besagt, dass die Informatik mit einem starken Verständnis ihrer eigenen Grenzen geboren wurde. Er schätzte, dass die Informatik das einzige bekannte Gebiet des wissenschaftlichen Diskurses ist, das mit einem solchen Bewusstsein geboren wurde – im Gegensatz zu anderen Wissenschaften, die ihre eigenen Grenzen, wie wir alle, erst im späten Mittelalter erkennen.

Es dauerte nicht lange, nachdem Turings Ideen (und ähnliche Ideen von anderen) in den ersten Computern verkörpert wurden, dass Wissenschaftler mit Fragen über die inhärenten Fähigkeiten und Grenzen der Maschinen konfrontiert wurden. In den frühen 1950er Jahren prahlte John von Neumann, der ungarisch-amerikanische Pionier des modernen Computers, mit einem Algorithmus, der im Vergleich zum exponentiellen Amtsinhaber polynomisch sei, wie sich Papadimitriou erinnerte – er habe einen langsamen Algorithmus mit einem schnellen überlistet. Dies war der Beginn einer neuen Theorie: Computational Complexity Theory. Der springende Punkt dabei war, dass nur polynomiale Algorithmen in irgendeiner Weise gut oder praktisch sind oder es wert sind, auf ein Problem zu zielen, während ein exponentieller Algorithmus, sagte Papadimitriou, das algorithmische Äquivalent zum Tod ist.

Cook begann Mitte der 1960er Jahre erstmals über Komplexität nachzudenken. Während er an seiner Doktorarbeit in Harvard arbeitete, überlegte er, ob es möglich ist, mit bestimmten Rechenmodellen zu beweisen, dass Multiplikation schwieriger ist als Addition (es bleibt ein offenes Problem).

Laut einem Buch über Cook, das 1967 von der Association for Computing Machinery (ACM) veröffentlicht wurde, entwarf er während seines Postdoc-Aufenthalts in Berkeley Kursnotizen, die den Keim für sein großes Ergebnis enthielten. Er hatte eine Formulierung der Komplexitätsklassen ausgearbeitet, die später als P und NP bekannt wurden, und stellte die Frage, ob P gleich NP sei. (Ungefähr zur gleichen Zeit kreisten andere, darunter der Informatiker Jack Edmonds, der inzwischen von der University of Waterloo im Ruhestand ist, um dieselben Ideen.)

Aber das Gebiet der Informatik stand noch ganz am Anfang, und für die meisten Wissenschaftler und Mathematiker waren solche Ideen ungewohnt, wenn nicht geradezu seltsam. Nach vier Jahren an der mathematischen Fakultät von Berkeley wurde Cook für eine Anstellung in Betracht gezogen, aber keine Stelle angeboten. Er hatte Anwälte in der neuen Fakultät für Informatik der Universität, und sie setzten sich dafür ein, dass ihm eine Stelle in ihren Reihen gewährt wurde, aber der Dekan war nicht geneigt, jemandem eine Anstellung zu geben, den die berühmten Mathematiker abgelehnt hatten.

Die meisten Komplexitätstheoretiker träumen etwas kleiner und entscheiden sich stattdessen für indirekte Ansätze.

Präsidentschaftsvorhersage von nate Silver für 2016

1970 wechselte Cook an die University of Toronto. Im folgenden Jahr veröffentlichte er seinen Durchbruch. Eingereicht auf einem Symposium der ACM, das im Mai in Shaker Heights, Ohio, stattfand, schärfte das Papier das Konzept der Komplexität und definierte einen Weg, die schwierigsten Probleme in NP zu charakterisieren. Es bewies in einem Blitz algorithmischer Alchemie, dass ein Problem, das als Erfüllbarkeitsproblem bekannt ist (Suche nach einer Lösung für eine Formel unter gegebenen Bedingungen), in gewissem Sinne das schwierigste Problem in NP war, und dass alle anderen NP-Probleme darauf reduziert werden könnte.

Dies war ein entscheidendes Theorem: Wenn es einen Polynomzeitalgorithmus gibt, der das Erfüllbarkeitsproblem löst, dann dient dieser Algorithmus als Skelettschlüssel, der Lösungen für alle Probleme in NP aufschließt. Und wenn es für alle Probleme in NP eine polynomielle Lösung gibt, dann ist P = NP.

Unter Informatikern ist Cooks Theorem ikonisch. Leslie Valiant aus Harvard erinnerte sich auf dem Symposium 2019 genau daran, wo und wann er zum ersten Mal davon gehört hatte. Nach Abschluss seines Grundstudiums in Mathematik hatte er eine Promotion in Informatik begonnen. Es gebe zwar Kurse und Abschlüsse in diesem noch jungen Gebiet, aber es fühle sich kurzlebig an, vielleicht fehle es an tiefgründigem intellektuellem Inhalt. Es war eine ernsthafte Sorge für Leute, die sich damals mit Informatik beschäftigten, sagte er. Sie fragten: „Ist das ein Acker? Wohin geht es?‘ Eines Tages stieß Valiant auf Cooks Papier. Er las es über Nacht. Ich war verwandelt, sagte er. Im Handumdrehen waren meine Bedenken bezüglich der Informatik sehr stark reduziert. Dieses Papier – für mich hat es wirklich das Feld erobert. Ich denke, es hat die Informatik gemacht – hat sie zu etwas Substanziellem gemacht.

Und dann, wie die Geschichte erzählt, kam nach Cooks Theorem eine Sintflut.

1972 demonstrierte Dick Karp, ein Computerwissenschaftler in Berkeley, nachdem er Cooks esoterischen Aufsatz gelesen hatte, dass viele der klassischen Computerprobleme, mit denen er bestens vertraut war – im Wesentlichen jedes Problem, das er nicht zu lösen wusste und das aus der mathematischen Programmierung stammte, Operations Research, Graphentheorie, Kombinatorik und Computerlogik – besaßen die gleiche Transformationseigenschaft, die Cook beim Erfüllbarkeitsproblem gefunden hatte. Insgesamt fand Karp 21 Probleme, darunter das Rucksackproblem (Suche nach dem optimalen Weg, einen begrenzten Raum mit den wertvollsten Gegenständen zu packen), das Problem des Handlungsreisenden (Finden der kürzestmöglichen Route, die jede Stadt einmal besucht und in die Stadt zurückkehrt). des Ursprungs) und das Steiner-Baum-Problem (versucht, eine Menge von Punkten optimal mit Liniensegmenten minimaler Gesamtlänge zu verbinden).

Karp zeigte, dass diese spezielle Sammlung von Problemen alle gleichwertig waren, was wiederum zeigte, dass das von Cook identifizierte Muster kein isoliertes Phänomen war, sondern eher eine Klassifizierungsmethode von überraschender Kraft und Reichweite. Es war eine Art Lackmustest, der die Klasse der sogenannten NP-vollständigen Probleme identifizierte: Eine Lösung für irgendein Problem würde sie alle knacken.

Papadimitriou hält NP-Vollständigkeit für ein vielseitiges Werkzeug. Wenn Sie ein Problem nicht lösen können, versuchen Sie zu beweisen, dass es NP-vollständig ist, denn das spart Ihnen vielleicht viel Zeit, sagte er in der öffentlichen Vorlesung – Sie können auf eine exakte Lösung verzichten und mit der Lösung einer Näherung fortfahren oder Variation des Problems statt.

Im großen Bogen der Geschichte sieht Papadimitriou das Phänomen der NP-Vollständigkeit und die Suche nach P vs. NP als das Schicksal der Informatik. Denn wie es der wissenschaftliche Zufall will, kam ein sowjetischer Mathematiker, Leonid Levin, mehr oder weniger zur gleichen Zeit zu einem Ergebnis, das dem von Cook entsprach. Levin, jetzt an der Boston University, arbeitete hinter dem Eisernen Vorhang. Nachdem es größere Beachtung gefunden hatte (er wanderte 1978 nach Amerika aus), wurde das Ergebnis als Cook-Levin-Theorem bekannt.

Und in einer weiteren Coda etwa ein Jahrzehnt später wurde ein verlorener Brief in den Princeton-Archiven des österreichischen Logikers Kurt Gödel entdeckt. 1956 hatte er an von Neumann geschrieben und gefragt, ob ein logisches Problem – das im modernen Sprachgebrauch als NP-vollständig bezeichnet würde – in polynomieller Zeit gelöst werden könnte. Er meinte, dass dies Folgen von größter Tragweite haben würde.

Billardkugeln

Das Cliquenproblem: Suchen Sie in einem Diagramm nach Cliquen, z. B. einer bestimmten Untergruppe von Freunden in einem sozialen Netzwerk.

DEREK BRAHNEY

Vier. Während ein halbes Jahrhundert Arbeit nicht annähernd zu einer Lösung geführt hat, beflügeln einige Ergebnisse zumindest die Vorstellungskraft: Ein Artikel aus dem Jahr 2004 beanspruchte einen Beweis für P = NP unter Verwendung von Seifenblasen als Mechanismus der analogen Berechnung (Seifenfilm natürlich Ausrichtung in der Minimalenergiekonfiguration, löst das NP-vollständige Steinerbaumproblem in gewisser Weise).

Heutzutage ist es ein seltener Vogel von Informatikern – zum Beispiel Ron Fagin, ein IBM-Stipendiat – der das Problem frontal anpackt. In den 1970er Jahren stellte er den Satz von Fagin auf, der die Klasse NP in Bezug auf die mathematische Logik charakterisierte. Und er hat das Problem mehr als einmal gelöst, aber die Ergebnisse standen nie länger als ein paar Tage, bevor er einen Fehler fand. Fagin erhielt vor Kurzem Fördergelder für ein P vs. NP-Projekt aus dem Exploratory Challenges-Programm von IBM zur Unterstützung abenteuerlicher Forschung. Um zu erklären, warum er dabei bleibt, zitiert er gern Theodore Roosevelt, der sagte, es sei viel besser, Großes zu wagen, als zu denen zu gehören, die in einem grauen Zwielicht leben, das weder Sieg noch Niederlage kennt.

Aber die meisten Komplexitätstheoretiker träumen etwas kleiner und entscheiden sich stattdessen für indirekte Ansätze – das Problem zu kippen, es umzugestalten oder umzugestalten, verwandte Umgebungen zu erkunden und das Arsenal an Werkzeugen, die dagegen eingesetzt werden könnten, weiter zu reduzieren (viele sind heute als nutzlos bekannt). ).

Ryan Williams, Informatiker am MIT, versucht, das Problem sowohl von oben als auch von unten zu beleuchten – indem er die Natur von Obergrenzen und Untergrenzen bei Kernrechenproblemen untersucht. Eine Obergrenze ist, vereinfacht ausgedrückt, eine bestimmte mathematische Behauptung, dass es einen konkreten Algorithmus gibt, der ein bestimmtes Problem löst, ohne eine bestimmte Menge an Ressourcen (Zeit, Speicher, Energie) zu überschreiten. Eine Untergrenze ist das immaterielle Gegenteil: Es ist eine allgemeine Behauptung der Unmöglichkeit, die zeigt, dass es keinen solchen Algorithmus universell gibt. Ein Schwerpunkt von Williams’ Forschung ist es, untere Schranken konstruktiv und konkret zu machen – mathematische Objekte mit beschreibbaren Eigenschaften. Er glaubt, dass konstruktivere Ansätze für untere Schranken genau das sind, was uns in aktuellen Ansätzen der Komplexitätstheorie fehlt.

Williams hat die Wahrscheinlichkeit, dass P ≠ NP ist, auf ziemlich moderate 80 % festgelegt. Aber in letzter Zeit äußern einige Forscher auf diesem Gebiet Zweifel selbst an diesem Grad an Gewissheit. Ich frage mich immer öfter, ob P gleich NP ist, sagt Toniann Pitassi, Informatiker an der University of Toronto und ehemaliger Doktorand von Cook. Ihr Ansatz, das Problem zu umkreisen, besteht darin, sowohl vergrößerte als auch verkleinerte Analoga zu untersuchen, schwierigere und einfachere Modelle. Manchmal macht es die Verallgemeinerung der Frage klarer, sagt sie. Aber insgesamt hat sie keine Klarheit erlangt: Die meisten Leute denken, dass P nicht gleich NP ist. Und ich weiß es nicht. Vielleicht liegt es nur an mir, aber ich habe das Gefühl, dass es immer weniger klar wird, dass das die Wahrheit ist.

In der Vergangenheit, so Pitassi, seien überraschende Ergebnisse gelegentlich aus dem Nichts aufgetaucht – scheinbare Unmöglichkeiten, die von intelligenten Algorithmusdesignern als möglich bewiesen wurden. Dasselbe könnte mit P vs. NP passieren, vielleicht in weiteren 50 Jahren oder einem Jahrhundert. Eines der wichtigsten Ergebnisse der gesamten Komplexitätstheorie wurde beispielsweise 1989 von David Barrington von der University of Massachusetts, Amherst, erzielt machte sich daran, etwas zu tun, das scheinbar eine unbegrenzte Menge an Speicher benötigte, tatsächlich aber erstaunlich wenig verbrauchte – nur fünf Informationsbits, genug, um eine Zahl zwischen eins und 32 (einschließlich) oder ein Wort mit zwei Buchstaben anzugeben.

Ein neueres und verwandtes Ergebnis aus dem Jahr 2014 überraschte James Cook. Ausgehend von Barringtons Theorem verwendet es das Gedächtnis auf eine wunderbar seltsame Weise. Wie der Titel des Artikels von Harry Buhrman und Mitarbeitern von der Universität Amsterdam andeutet, geht es um das Rechnen mit vollem Gedächtnis. James kann den einleitenden Absatz des Papiers praktisch wortwörtlich herunterrattern:

Stellen Sie sich folgendes Szenario vor. Sie möchten eine Berechnung durchführen, die mehr Arbeitsspeicher benötigt, als Ihnen derzeit auf Ihrem Computer zur Verfügung steht. Eine Möglichkeit, dieses Problem zu lösen, besteht darin, eine neue Festplatte zu installieren. Wie sich herausstellt, haben Sie eine Festplatte, die jedoch voll mit Daten, Bildern, Filmen, Dateien usw. ist. Sie müssen im Moment nicht auf diese Daten zugreifen, möchten sie aber auch nicht löschen. Können Sie die Festplatte für Ihre Berechnung verwenden, möglicherweise ihren Inhalt vorübergehend ändern und sicherstellen, dass die Festplatte nach Abschluss der Berechnung wieder in ihrem ursprünglichen Zustand mit allen intakten Daten ist?

Die Antwort ist entgegen der Intuition ja.

James betrachtet es als geliehene Erinnerung. Nachdem der Schock über dieses Ergebnis angekommen war, hatte er Spaß daran, herauszufinden, wie er es auf ein bestimmtes Problem anwenden konnte – und dort weiterzumachen, wo sein Vater aufgehört hatte.

Vor ein paar Jahrzehnten wandte sich Steve Cook anderen verwandten Problemen der Komplexitätstheorie zu. Bei einem Problem stellte er eine Vermutung darüber an, wie viel Speicher ein Algorithmus benötigen würde, um das Problem zu lösen – und verfeinerte es auf das absolute Minimum. Im Jahr 2019 setzte James zusammen mit Ian Mertz, einem von Pitassis Doktoranden, die poetische Idee des Ausleihens von Erinnerungen um und bewies, dass noch weniger Gedächtnis benötigt wird. Das Ergebnis hat die Vermutung seines Vaters nicht ganz widerlegt, aber es ist dennoch ein kleiner Fortschritt bei der Suche nach der großen Komplexität.

Und Probleme in der Komplexitätstheorie, beobachtet James, haben manchmal einen Dominoeffekt – wenn es in einer kritischen Ecke einen Beweis gibt, dann fallen alle Dominosteine. Die bahnbrechenden Ergebnisse, die wichtigsten, stammen aus einer langen Reihe von Arbeiten vieler verschiedener Menschen, die schrittweise Fortschritte machen und Verbindungen zwischen verschiedenen Fragen herstellen, bis schließlich ein großes Ergebnis entsteht.

Er erwähnt auch einen Vorbehalt: Während ein wirklich teuflisch schneller P = NP-Algorithmus weltbewegend wäre, gibt es auch ein Szenario, in dem P = NP eine Enttäuschung sein könnte. Es könnte sich herausstellen, dass ein P-Algorithmus, der das NP-vollständige Problem lösen kann, auf einer Zeitskala von beispielsweise n ^100. Technisch gesehen fällt das unter P: Es ist ein Polynom, sagt James. Aber n ^100 ist immer noch sehr unpraktisch – es würde bedeuten, dass größere Probleme auf menschlicher Zeitskala immer noch unerreichbar wären.

Das setzt natürlich voraus, dass wir den Algorithmus überhaupt finden können. Donald Knuth, ein Algorithmus in Stanford, hat in den letzten Jahren seine Meinung geändert – er hat das Bit umgedreht. Seine Intuition ist, dass P zwar gleich NP ist, dass wir diese Tatsache aber praktisch nie ausnutzen können – weil wir keinen der zufällig funktionierenden Algorithmen wirklich kennen werden. Es gibt eine verblüffende Anzahl von Algorithmen da draußen, erklärt er, aber die meisten von ihnen entziehen sich unserer Vorstellungskraft. Während also einige Forscher darauf bestehen, dass kein P = NP-Algorithmus existiert, behauptet Knuth, dass es wahrscheinlicher ist, dass kein Polynomialzeit-Algorithmus jemals von einfachen Sterblichen verkörpert – tatsächlich als Programm niedergeschrieben – wird.

Für Papadimitriou würde jede Antwort eine lebenslange Besessenheit löschen. Er glaubt, dass das P vs. NP-Problem in den Bereich grundlegender wissenschaftlicher Rätsel wie dem Ursprung des Lebens und der Vereinigung der Kraftfelder der Natur gehört. Es ist die Art von tiefgründigem, konsequentem Rätsel, konkret und doch universell, sagte er, das nicht nur der Wissenschaft, sondern dem menschlichen Leben selbst Bedeutung verleiht.

Stellen Sie sich vor, wir haben Glück und können diesem Planeten trotz aller Widrigkeiten noch ein paar tausend Jahre entziehen, sagte er. Und wir lösen diese Probleme nicht. Was ist der Punkt?!

Tatsächliche Technologien

Kategorie

Unkategorisiert

Technologie

Biotechnologie

Technologierichtlinie

Klimawandel

Mensch Und Technik

Silicon Valley

Computer

Mit News Magazine

Künstliche Intelligenz

Platz

Intelligente Städte

Blockchain

Reportage

Alumni-Profil

Alumni-Verbindung

Mit News Feature

1865

Meine Sicht

77 Mass Avenue

Treffen Sie Den Autor

Profile In Großzügigkeit

Auf Dem Campus Gesehen

Alumni-Briefe

Nachrichten

Wahl 2020

Mit Index

Unter Der Kuppel

Feuerwehrschlauch

Unendliche Geschichten

Pandemie-Technologieprojekt

Vom Präsidenten

Titelstory

Fotogallerie

Empfohlen