Konsequenzen eines quasi-polynomialen Zeitalgorithmus für das Graphisomorphismusproblem

Das Graph Isomorphism Problem (GI) ist wohl der bekannteste Kandidat für ein NP-intermediäres Problem. Der bekannteste Algorithmus ist der subexponentielle Algorithmus mit einer Laufzeit von . Es ist bekanntdass GI nichtNP-komplette es sei denndiePolynomialzeitHierarchiezusammenbricht.$2^{O(\sqrt{n \log n})}$$\mathsf{NP}$

Was wären die komplexitätstheoretischen Konsequenzen eines quasi-polynomialen Zeitalgorithmus für das Graph-Isomorphismus-Problem?
Würde ein quasi-polynomialer Zeitalgorithmus für GI irgendwelche berühmten Vermutungen in der Komplexitätstheorie widerlegen?

Andere ähnliche Probleme wie das Problem der minimalen dominierenden Menge in Turnieren, das Problem des Gruppenisomorphismus und das Problem des Turnierisomorphismus weisen Algorithmen mit quasi-polynomialer Zeit ( QP ) auf. Die beiden letzteren Probleme sind polynomialzeitreduzierbar auf GI.

Können wir das Problem der minimalen dominierenden Menge in Turnieren effizient auf GI reduzieren?
Gibt es eine Vermutung, die ausschließt, dass GI schwer für QP ist?

Update (14.12.2015) : Babai hat einen vorläufigen Entwurf zu seinem Algorithmus für die Quasipolynomialzeit für GI auf arXiv veröffentlicht.

Update (2017.01.04) : Babai eingezogene die Behauptung , dass der Algorithmus in Quasipolynom Zeit ist, nach der neuen Analyse des Algorithmus in subexponentiellen Zeit der innerhalb von2 n o ( 1 ) liegt .$\exp \exp(\tilde{O}(\sqrt{\lg n}))$$2^{n^{o(1)}}$

Update (09.01.2017) : Babai hat die quasipolynomiale Zeitangabe wieder eingeführt und das Verfahren durch ein effizienteres ersetzt.

Soweit ich das beurteilen kann, denke ich, ist die Antwort sehr gering, wenn Sie einfach nach den Konsequenzen der Tatsache fragen (als Black Box), dass GI in QP ist. Das einzige , was ich denken kann, was kein Satz ist , sondern eine Folge für Forschungsrichtungen ist zu Gruppe Isomorphismus. Da GroupIso auf GI reduziert wird und wir nicht einmal wissen, ob GroupIso in P enthalten ist, kann das Einfügen von GroupIso in P als ein wichtiges Hindernis für das Einfügen von GI in P angesehen werden (wenn Sie glauben, dass letzteres der Fall sein könnte).

$n^{\log n + O(1)}$$2^{\tilde O(\sqrt{n})}$

$\varnothing$$\Sigma^*$

Was wären die komplexitätstheoretischen Konsequenzen eines quasi-polynomialen Zeitalgorithmus für das Graph-Isomorphismus-Problem?

Mehr oder weniger ähnlich zu den Konsequenzen des deterministischen Polynom-Zeit-Algorithmus für die Primalitätsprüfung, des deterministischen Polynom-Zeit-Algorithmus für die lineare Programmierung und dem anderen Fall, in dem praktisch effiziente (randomisierte) Algorithmen (mit seltenen pathologischen Beispielen, in denen der Algorithmus ineffizient wurde) bekannt waren und seit langer Zeit im Einsatz. Dies bestätigt die Vermutung, dass die praktische Effizienz ein guter Indikator für die Existenz deterministischer theoretischer Algorithmen ist, die die Probleme der seltenen pathologischen Beispiele überwinden.

Würde ein quasi-polynomialer Zeitalgorithmus für GI irgendwelche berühmten Vermutungen in der Komplexitätstheorie widerlegen?

Nein, die Vermutungen gehen eher auf die entgegengesetzte Seite, nämlich dass GI in P ist. Da GI in NP ist, wird es nicht möglich sein, diese Art von Vermutungen bald zu widerlegen.

Können wir das Problem der minimalen dominierenden Menge in Turnieren effizient auf GI reduzieren?

Die minimale dominierende Menge ist kein Isomorphismusproblem, daher gibt es keinen Grund, warum zu erwarten ist, dass sie auf den GI reduziert werden kann.

Gibt es eine Vermutung, die ausschließt, dass GI schwer für QP ist?

Wir wissen nicht einmal, wie man das String-Isomorphismus-Problem auf GI reduziert, und dies ist zumindest ein Isomorphismus-Problem. Babais Beweis zeigte, dass der String-Isomorphismus in QP vorkommt. Und was soll QP eigentlich nur schwer bedeuten? Schwer unter Polynomzeitverkürzungen?

Aus der Einführung von On the Group und Color Isomorphism Problems von François Le Gall und David J. Rosenbaum

Die Komplexität der Isomorphismustestprobleme ist es wert, untersucht zu werden, da es sich um grundlegende Rechenfragen handelt und viele von ihnen nicht in P vorliegen, aber dennoch einfacher zu sein scheinen als die NP-vollständigen Probleme. Das am intensivsten untersuchte ist das Graph-Isomorphismus-Problem.

$\mathsf{GI}^*$$\mathsf{GrI}^*$definiert sind (in der obigen Abhandlung, aber die Autoren fragen sich zu Recht, warum es niemand zuvor getan hat), die die fehlenden Teile aus dem String-Isomorphismus-Problem hinzufügen. (Und das Problem der Farbisomorphie ist nur ein anderer Name für das Problem der String-Isomorphie. Das Problem der Namensfarbautomorphie geht auf die ersten Arbeiten von Babai und Luks zurück, die Namens-String-Isomorphie tritt später in ihrer Arbeit zur kanonischen Kennzeichnung auf.)

$\mathsf{GI}^*$

Bearbeiten: Diese Antwort wurde im Zusammenhang mit der Rücknahme von Babais Ergebnis gegeben, bevor er eine Lösung ankündigte. Dies legt nahe, dass die leichte Verallgemeinerung des Graphisomorphismusproblems, die durch das Stringisomorphismusproblem vorgeschlagen wird, das wirklich wichtige Problem ist. Die implizite Erwartung hier ist, dass jeder vernünftige Algorithmus für das Graphisomorphismusproblem zu einem ähnlichen Algorithmus für das verallgemeinerte Graphisomorphismusproblem führt. Das verallgemeinerte Problem ist Polynomzeit äquivalent zu dem Set-Stabilisator Problem , die Gruppe Kreuzungsproblem , das coset Kreuzungsproblem, das Set - Transporter Problem , ... Die Idee hinter dieser Erwartung ist , dass die verallgemeinerte Problem in dem auftreten wird rekursiven Teilvon jedem vernünftigen Algorithmus, so muss es trotzdem angesprochen werden. (Und es ist durchaus möglich, dass das verallgemeinerte Problem die Polynomzeit ist, die dem Graphisomorphismus entspricht.)

Jetzt deuten die Kommentare von Joshua Grochow darauf hin, dass es mir nicht gelungen ist, die konzeptionelle Bedeutung der fehlenden Teile aus dem String-Isomorphismus-Problem zu erklären. Für unendliche Strukturen ist es möglicherweise einfacher zu erkennen, dass ein gültiger Isomorphismus nicht nur die gegebene Struktur bewahren sollte, sondern auch zu einer geeigneten Kategorie von Funktionen gehört (zum Beispiel der Kategorie kontinuierlicher Funktionen). Bei endlichen Strukturen tritt das analoge Phänomen meist bei Quotientenstrukturen auf, bei denen die entsprechende Funktionskategorie mit den angegebenen Quotienten kompatibel sein sollte. Das Johnson-Zeug ist ein typisches Beispiel für solche Quotienten, zum Beispiel arbeitet die Partitionslogik über die beiden Elementteilmengen einer Basismenge. Beachten Sie auch, dass das Einschränken der zulässigen Kategorie für die Isomorphismen häufig das Problem des Isomorphismustests erleichtert.

Das Problem mit Verallgemeinerungen des Graph-Isomorphismus-Problems ist, wo es aufhören soll. Warum nicht so weit verallgemeinern, dass das Permutationsgruppen-Isomorphismus-Problem einbezogen wird? Diese Frage ist wirklich schwierig, da viele nicht triviale Ergebnisse für den Graphisomorphismus wahrscheinlich auch auf den Permutationsgruppenisomorphismus übertragen werden. Aber hier ist es vernünftiger, die rechnergestützte Permutationsgruppentheorie als eigenständiges Thema zu behandeln, auch wenn sie tatsächlich in engem Zusammenhang mit dem Problem des Graphisomorphismus steht.