Dieser Artikel erschien ursprünglich auf Motherboard Deutschland. Seit seiner ursprünglichen Veröffentlichung wurde es mit neuen Informationen von Motherboard US aktualisiert. Was haben heilbarer Krebs, fairer Kapitalismus und das perfekte Spiel von Super Mario Bros. gemeinsam? Nach einer mathematischen Theorie würde die Lösung eines dieser Probleme es uns ermöglichen, die anderen schnell zu lösen., Alles, was benötigt wird, sind bessere Algorithmen, um zu beweisen, dass komplizierte Fragen—wie Proteinfaltung, effiziente Marktplätze und kombinatorische Analysen—nur Variationen einfacherer Probleme sind, die Supercomputer bereits lösen können. Aber wie kann ein Algorithmus extrem komplizierte Probleme vereinfachen? Das hängt von einer anderen Frage ab: Was ist, wenn komplizierte Probleme wirklich nur einfache verschleierte Probleme sind?, Dieses Rätsel bleibt eine der größten ungelösten Fragen der modernen Mathematik und ist eines der sieben Millennium-Preisprobleme, für die jede akzeptierte Antwort mit einer Million Dollar belohnt wird.
Nun hat ein deutscher Mann namens Norbert Blum behauptet, das obige Rätsel gelöst zu haben, das als P vs NP-Problem bekannt ist. Leider trägt seine angebliche Lösung keine guten Nachrichten., Blum, der von der Universität Bonn stammt, behauptet in seinem kürzlich veröffentlichten 38-seitigen Papier, dass P nicht gleich NP ist. Mit anderen Worten, komplizierte Probleme unterscheiden sich grundlegend von einfachen Problemen, und es sieht nicht so aus, als könnten unsere Hochleistungscomputer diese schwierigsten Probleme in naher Zukunft jederzeit lösen. Und in den Tagen seit seiner Veröffentlichung haben zahlreiche Mathematiker begonnen, Fragen zu stellen, ob Blum es überhaupt gelöst hat.
Was genau ist das P-versus-NP-Problem?,
Die meisten Informatiker neigen dazu, Blums Schlussfolgerung zuzustimmen. Harte Probleme sind hart, leichte Probleme sind einfach. In der Informatik fallen einfache Probleme normalerweise unter das Banner von P. Dies bedeutet, dass sie in „Polynomzeit“ gelöst werden können, was sehr ähnlich ist, als würde man sagen, dass sie in einem vernünftigen Zeitraum gelöst werden können. Viel schwieriger sind die NP-Probleme, die Computer in einem vernünftigen Zeitrahmen nicht lösen können. Aus praktischen Gründen können NP-Probleme auch nur von Computern unlösbar sein., (Beachten Sie jedoch, dass NP für „nichtdeterministische Polynomzeit“ und nicht für „nicht polynomische“ Zeit steht.) Hier sind einige Beispiele für NP-Probleme:
der Protein-Faltung: Der Prozess, durch den Proteine in einer biologischen Organismus erhalten Ihre Struktur. Ein besserer Einblick in diesen Prozess könnte uns helfen, Mutationen zu erkennen oder sogar zu behindern, die bestimmte Formen von Krebs heilen könnten. Optimierte Routenfindung: Eine optimierte Reiseroute durch 15 verschiedene Städte, ohne die gleiche Stadt zweimal zu besuchen?, Eine harte Nuss zu knacken, auch für einen Supercomputer, weshalb dies auch in der Informatik als wichtiges Problem angesehen wird.
Das perfekte Schachspiel: Ein Schachspiel hat unendlich viele Züge, so dass selbst ein Supercomputer mit unglaublicher Kapazität keine perfekte Taktik bestimmen kann. Viele Mathematiker halten dieses Problem für so schwierig, dass sie es nicht für ein NP-Problem halten, sondern es für völlig außerhalb des Bereichs der Möglichkeiten betrachten.,
All diese komplexen Probleme haben eines gemeinsam: So schwierig es auch sein mag, eine Lösung für NP-Probleme zu finden, es ist relativ einfach, die Gültigkeit der Lösungen zu überprüfen, sobald Sie sie haben.
Diese beiden kategorischen Unterschiede in der Problemkomplexität haben ihren Ursprung vor dem gesellschaftlichen Aufstieg von Heimcomputern. In den 1970er Jahren, als Computer noch die Größe eines klobigen Kühlschranks hatten, wurde schnell festgestellt, dass nicht alle Probleme der Menschheit einfach durch diese Maschinen gelöst werden konnten., Es wurde vorgeschlagen, dass die Unterscheidung in Bezug auf die Rechenkomplexität formalisiert werden könnte, was zu einer Reihe von Komplexitätsklassen führt, einschließlich N und NP.
Seit der formalen Definition von P und NP im Jahr 1971 haben Informatiker diskutiert, ob es möglich wäre, einen Algorithmus zu entwickeln, der in der Lage ist, NP-Probleme so zu reduzieren oder neu zu definieren, dass sie in polynomialer Zeit gelöst werden können. Sollte jemand beweisen können, dass alle NP-Probleme letztendlich nur Variationen von P-Problemen sind, dann würden alle NP-Probleme im Wesentlichen der gleichen Form der Reduktion unterliegen., Mit anderen Worten, wer die perfekte Super Mario Bros.-Taktik kennt, könnte auch Krebs heilen.
Insgesamt haben 116 der Mutigsten auf ihrem Gebiet offiziell versucht, dieses Rätsel zu lösen (obwohl unzählige weitere Informatiker Lösungen für Messageboards und Websites wie arXiv veröffentlicht haben). Bis heute wurde keiner dieser Beweise offiziell von der mathematischen Gemeinschaft anerkannt.
Eine Art Wer will Millionär werden?, für Mathematiker
Im Jahr 2000 stellte das Clay Mathematics Institute (CMI) in Oxford eine Liste von sieben ungelösten Millennium-Preisproblemen zusammen und versprach eine Million Dollar für jede Lösung. Es ist eine Art Wer will Millionär werden? oder X-Preis für Mathematiker. Die Millennium-Preisprobleme gelten selbst in Expertenkreisen als außergewöhnlich schwierig. Eine Fülle von feldspezifischen Kenntnissen ist notwendig, um die Fragen überhaupt zu verstehen., Das einzige bisher gelöste Millennium-Preisproblem ist die Poincaré-Vermutung, die in einem Artikel über ein anderes mathematisches Konzept nicht so leicht als Ausnahme erklärt werden kann.
Die Lösung des NP-Problems wäre keine ganz gute Sache. Zum Beispiel basiert die meiste Verschlüsselung auf der Schwierigkeit, sehr große Primzahlen zu berücksichtigen. Integer-Faktorisierung ist ein Klasse-NP-problem. Ein 256-Bit-Code, wie ihn Finanzinstitute bei Online-Kreditkartenzahlungen verwenden, gilt als unzerbrechlich und daher sehr sicher., Sollte jemand beweisen, dass NP gleich P tut, Banken müssten schnell mit einer anderen Sicherheitsmethode kommen.
Was halten Mathematiker von Blums mathematischem Beweis?
Seit Blums Papier veröffentlicht wurde, rätseln Mathematiker und Informatiker weltweit, ob der Bonner Forscher tatsächlich dieses Millennium-Preisproblem gelöst hat. Nach einer anfänglich positiven Reaktion, wie der des Stanford-Mathematikers Reza Zadeh, beginnen Zweifel aufkommen, ob Blums Argumentation richtig ist.,
In einem Forum für theoretische Mathematik wandte sich ein Benutzer namens Mikhail an Alexander Razborov—den Autor der Arbeit, auf der Blums Beweis basiert -, um ihn nach Blums Papier zu fragen. Razborov gibt vor, einen Fehler in Blums Papier entdeckt zu haben: Blums Hauptargument widerspricht einer von Razborovs Schlüsselannahmen. Und Mathematiker Scott Aaronson, wer ist so etwas wie eine Autorität in der mathematischen Gemeinschaft, wenn es um P kommt vs., NP, sagte, er wäre bereit, $ 200,000 zu wetten, dass Blums mathematischer Beweis nicht ertragen wird. „Bitte hör auf zu fragen“, schreibt Aaronson. Wenn der Beweis nicht widerlegt wurde, “ können Sie zurückkommen und mir sagen, dass ich ein geschlossener Narr war.“In der Woche seit Aarons erstem Blogbeitrag haben andere Mathematiker begonnen, Löcher in Blums Beweis zu stecken. Dick Lipton, ein Informatikprofessor an der Georgia Tech, schrieb in einem Blogbeitrag, dass Blums Beweis „viele Filter der Ernsthaftigkeit passiert“, schlug jedoch vor, dass es einige Probleme damit geben könnte., Ein Kommentator in diesem Blogbeitrag, der nur als „Vloodin“ bekannt ist, stellte fest, dass der Beweis einen „einzigen Fehler an einem subtilen Punkt“ enthielt; Andere Mathematiker haben seitdem Vloodins anfängliche Analyse eingespielt und bestätigt, und so besteht der aufkommende Konsens unter vielen Mathematikern darin, dass eine Lösung für P vs. NP schwer fassbar bleibt. Übersetzt von Melina McCormack.