Wurde das Graph-Isomorphismus-Problem gelöst?

13

Wikipedia's Graph Isomorphism Problem Seite scheint darauf hinzudeuten, dass es nicht gelöst wurde. Ein Freund von mir wies jedoch auf einen polynomialen Zeitalgorithmus für den Graphisomorphismus hin . Ich bin nicht raffiniert genug, um der Argumentation in der Zeitung zu folgen.

Ich habe meinen eigenen sehr groben Versuch mit einem Polynomialzeitalgorithmus ohne irgendetwas Beweis, aber ich möchte wissen, ob dieses Problem erfolgreich gelöst wurde oder nicht, bevor ich fortfahre.

Ist das Graph-Isomorphismus-Problem also gelöst?

complexity-theory reference-request time-complexity graph-isomorphism Tyler Spaeth
quelle
1
lohnende Frage. Bei einem Cyber-Peer-Review wäre es besser, wenn die Befragten / Antworten tatsächlich auf bestimmte Fehler in der Arbeit hinweisen würden und nicht auf allgemeine Aspekte. Zugegebenermaßen ist hier jedoch zu bedenken , was professionelle Wissenschaftler über diese Art von Bemühungen denken. arxiv ist voll von fehlerhaften Papiere, viele auf P vs NP aber viele andere semifamous Probleme attract Amateur Bemühungen, zB auch die Collatz - Vermutung, Primzahlzwillinge, Goldbach - Vermutung, usw.
VZN
7
@vzn Ich glaube nicht, dass es Sinn macht, unsere Zeit damit zu verschwenden, Zeitungen zu lesen, die mit ziemlicher Sicherheit falsch sind und kein neues Licht auf das Problem werfen.
Yuval Filmus
2
@vzn Ich verstehe deine Beschwerde nicht. Die Antwort von DW (eine Stunde vor Ihrem Kommentar veröffentlicht) verweist auf einen Kommentar, der auf einen bestimmten Fehler in dem zur Diskussion stehenden ArXiv-Artikel hinweist.
David Richerby
2
@vzn Das ArXiv-Papier enthält einen Fehler. Es wurde nicht überarbeitet, um diesen Fehler zu beheben. Es ist keine weitere Begutachtung durch Fachkollegen erforderlich. Ich habe keine Ahnung, was Sie sagen, ist aus zweiter Hand: Ein Gegenbeispiel ist ein Gegenbeispiel, unabhängig davon, ob es Ihnen von seinem Entdecker oder von dem Drogendealer mitgeteilt wurde, der sich hinter dieser schäbigen Bar aufhält die Autobahn.
David Richerby
1
@vzn Vermutlich wurde es nicht überarbeitet, da der Autor den Fehler nicht beheben konnte. Beachten Sie, dass ArXiv das Zurückziehen von Manuskripten nicht zulässt, auch wenn sie sich als falsch herausstellen.
David Richerby

Antworten:

23

Nein, das Papier scheint fehlerhaft zu sein. Der Fehler wurde in einem Kommentar von Tracy Hall zu MathOverflow erklärt . In einem Folgekommentar wird behauptet, der Autor habe später einen Fehler in seinem Algorithmus festgestellt.

Wie Yuval erklärt, ist es nicht ungewöhnlich, dass Amateure versuchen, diese Probleme zu lösen. Sie neigen dazu, fehlerhaft zu sein. Wenn es um Ergebnisse zu bekannten offenen Problemen geht (z. B. P gegen NP, Graphisomorphismus usw.), empfehle ich, in renommierten Peer-Review-Konferenzen und -Zeitschriften nach veröffentlichter Literatur zu suchen haben eine viel höhere Wahrscheinlichkeit, richtig zu sein.

DW
quelle
17

Nein, das Graph-Isomorphismus-Problem wurde nicht gelöst. Der Artikel, auf den Sie verlinken, stammt aus den Jahren 2007–2008 und wurde von der breiteren wissenschaftlichen Community nicht akzeptiert. (Wenn es gewesen wäre, hätte ich es gewusst.)

Der Graph-Isomorphismus zieht, wie viele andere berühmte Probleme, viele Versuche von Amateuren an. Sie liegen fast immer falsch. Ich würde davon abraten, dieses Problem anzugehen, ohne erst in der Mathematik auf Forschungsebene kompetent zu werden.

Yuval Filmus
quelle
2
Eine andere Möglichkeit, mit solchen Forderungen von Experten umzugehen, sind Unmöglichkeits- oder Barriereergebnisse. Eine aussagekräftigere Gegenargumentation lautet: "Die Arbeit verwendet ein Argument vom Typ [x], um das Isomorphismusproblem zu lösen, aber aus der [a, b, c] -Forschung ist bekannt, dass es für diesen Typ ein spezifisches Hindernis gibt der Ansatz, und das Papier scheint diese Barriere nicht zu kennen oder offen zu legen, wie es überwunden wird. " Hierüber sind Ergebnisse für das Isomorphismusproblem und andere Schlüsselprobleme bekannt, z. B. P vs NP.
vzn
1
Der Versuch, ungelöste Probleme wie diese zu lösen (und zu scheitern ...), kann eine sehr fruchtbare Lernübung sein, wenn man mit der richtigen Einstellung eintritt.
Nick Alger
Es gibt jedoch einige Unstimmigkeiten : Beweise / Behauptungen haben eine gewisse Gültigkeit, die von der "Akzeptanz durch die breitere wissenschaftliche Gemeinschaft" und deren Kenntnis durch bestimmte Personen unabhängig ist. Wenn beispielsweise ein korrekter Beweis zum ersten Mal vorgelegt wird, wird er von niemand anderem als dem Autor sofort "akzeptiert". Weitere Unterstützung für diese Dynamik finden Sie in der Mathematikgeschichte. & Manchmal können zwischen der Einführung von Ansprüchen / Behauptungen und der Annahme lange Zeiträume liegen, z. B. im Fall von Galois, Ramanujan usw.
vzn
8

Ich wäre sehr zweifelhaft, dass dies der Fall ist (im Sinne des Beweises der Existenz eines polynomialen Zeitalgorithmus). Obwohl es nicht unmöglich ist, dass das Papier korrekt ist, gibt es eine Reihe von Warnzeichen:

  1. Der Autor hat das Ergebnis nicht in einem von Fachleuten geprüften Veranstaltungsort veröffentlicht (auch nicht nach 7 Jahren).
  2. Der Autor scheint nirgendwo etwas anderes veröffentlicht zu haben.
  3. Die Arbeit stellt die Algorithmen vor, aber der Anspruch auf Korrektheit ist ein informelles Argument über die Komplexität.
  4. Für ein Problem, das sich den Versuchen einiger sehr kluger Leute widersetzt hat, ist die Mathematik in der Zeitung zu einfach.
  5. Der Autor scheint keiner akademischen Einrichtung angeschlossen zu sein. Die neue Version des Papiers verdeutlicht dies.

Ohne jemanden, der einen Fehler im Papier identifiziert, handelt es sich nicht um idiotensichere Zeichen. Vielleicht hatte der Autor einen einzigartigen Einblick und wechselte dann zu einem völlig anderen Leben, aber das Gewicht der Wahrscheinlichkeit ist dagegen - außergewöhnliche Ansprüche erfordern außergewöhnliche Beweise.

Auszuarbeiten auf (4) angesichts dem jüngsten Nachrichten, László Babai vor kurzem behauptete , eine große Verbesserung gegenüber bekannten Graphisomorphie Algorithmus (keine Preprint noch nicht, aber ein ordentlicher Lauf Kommentar zu seiner öffentlichen Vorlesung findet sich hier ), einen pseudo-Polynomialzeitalgorithmus geben. Babai und seine Kollegen sind definitiv sehr kluge Leute, und die Mathematik, die verwendet wird, um dieses Ergebnis zu erhalten, ist schwierig, tief und erstreckt sich über Graphentheorie und Gruppentheorie. In Anbetracht des Gewichts der Wahrscheinlichkeit ist dies das erwartete Niveau für einen signifikanten Fortschritt bei einem Problem wie diesem.

Luke Mathieson
quelle
3
Die Punkte 1 bis 4 sind stark, aber 5 sind viel umständlicher.
David Richerby
(5) ist nicht korrekt. Die Institution ist (anscheinend) die Technische Universität Berlin und wird teilweise vom Staat gefördert. (1) von diesem Link / Paper-Crawler unterstützt. Das Papier ist auf der Woeginger Claims-Seite zitiert .
vzn
3
Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.
Raphael
quasipolynomial Claim wiederhergestellt
miracle173
3

Laszlo Babai gab an, seit dem 11. November 2015 eine quasipolynomiale Lösung für das Graph-Isomorphismus-Problem gefunden zu haben.

... und hat gestern (01.04.2017) die Klage zurückgenommen:

Quelle: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

bharv14
quelle
Aus dem von Ihnen angegebenen Link: Babai hat noch keinen Vorabdruck herausgebracht, und als ich ihn fragte, sagte er "bald, bald". Bis dahin.
Scaaahu
Die Frage definiert nicht, was es bedeuten würde, wenn das Graph-Isomorphismus-Problem als gelöst gewertet würde, aber die wahrscheinlichste Interpretation ist: Jemand hat einen Polynom-Zeit-Algorithmus dafür gefunden oder es gibt Beweise dafür, dass kein solcher Polynom-Zeit-Algorithmus existiert . Nach dieser Auslegung beantwortet diese Antwort die Frage nicht.
DW
4
Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.
Raphael
quasipolynomial Claim wiederhergestellt
miracle173