Konsequenzen eines quasi-polynomialen Zeitalgorithmus für das Graphisomorphismusproblem

40

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.2O(nlogn)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 .expexp(O~(lgn))2no(1)

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

Mohammad Al-Turkistany
quelle
6
Ich denke, viele Leute glauben, dass es einen polynomialen Zeitalgorithmus gibt, und AFAIK, ein solcher Algorithmus hätte keine komplexitätstheoretischen Konsequenzen.
Huck Bennett
7
AC0
14
Nach zwei Jahren, glaube ich, haben wir eine Antwort. Laszlo Babai hat bewiesen, dass GI einen quasi polynomialen Zeitalgorithmus besitzt. Quelle: lucatrevisan.wordpress.com/2015/11/03/…
user3415207
8
@ user3415207 Babai hat die Behauptung der quasipolynomialen Laufzeit zurückgezogen . Anscheinend gab es einen Fehler in der Analyse.
Raphael
6
@Raphael ... und Babai haben seine Behauptung wiederhergestellt (derselbe Link wie deiner).
Danny

Antworten:

5

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).

nlogn+O(1)2O~(n)

Joshua Grochow
quelle
nO(loglogn)
nO(loglogn)cc
@JoshuaGrochow Würden Sie mir zustimmen, dass der Ansatz von François Le Gall und David J. Rosenbaum in " Über die Probleme der Gruppen- und Farbisomorphie" Sinn macht? Oder zumindest, dass sie einige Fragen behandeln, die auftauchen könnten, nachdem sie ein grundlegendes Verständnis für das Ergebnis von László Babai gewonnen haben?
Thomas Klimpel
@ThomasKlimpel: Ich stimme zu, dass ihr Artikel Sinn macht, obwohl ich noch nicht weiß, wie ich ihre Einsichten nutzen kann (obwohl ich die meisten Beweise Babais verstehe).
Joshua Grochow
βkP
2

Σ

Emil Jeřábek unterstützt Monica
quelle
0

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.

GIGrIdefiniert 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.)

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.

Thomas Klimpel
quelle
1
Sn
1
@JoshuaGrochow Bei der Farb-ISO sind die Farben nur willkürliche Zahlen (wlog auf [n] beschränkt). Bei String-Iso werden die Strings über ein festes endliches Alphabet angegeben. Ich dachte, es sei ein binäres Alphabet, aber ich erinnerte mich daran. Ich erinnerte mich nur, dass ich anfangs verwirrt war, ob color iso nur ein anderer Name für string iso war. Als ich mich entschied, diese Zeitung zu lesen, nachdem Laszlo seine Behauptung zurückgezogen hatte, fühlte es sich für mich wie ein Unterschied an. Vielleicht ist es wirklich ein Unterschied, denn "über ein endliches Alphabet" kommuniziert "Fix deines endlichen Lieblingsalphabets, es macht keinen Unterschied". Was wahr ist.
Thomas Klimpel
1
logn[n]
1
@JoshuaGrochow Genau das, was ich damit gemeint habe, wird keinen Unterschied machen. "Das ist wahr. Ich habe jetzt versucht, Ihren Kommentar" String-Isomorphismus / Farb-Isomorphismus fällt nicht in diese Klasse "zu adressieren. Ich habe es genossen, einige Lektionen daraus zu lernen Andreas Blass und Yuri Gurevich auf dem Weg, die ebenfalls versuchen, sich auf konzeptionelle Punkte zu konzentrieren. Ich bin froh, dass Babai seinen Algorithmus jetzt korrigiert hat, sodass ich mich nicht gezwungen (oder unter Druck gesetzt) ​​fühle, zu untersuchen, ob Graphisomorphismus und Stringisomorphismus polynomielle Zeitäquivalente sind (In diesem Zusammenhang habe ich diese Antwort geschrieben.)
Thomas Klimpel
Ich bin verwirrt, warum Sie die Fortschritte bei der GI mit den Ergebnissen der Derandomisierung vergleichen.
Sasho Nikolov