Welche Beweise gibt es dafür, dass der Graphisomorphismus nicht in

23

Motiviert durch Fortnows Kommentar in meinem Beitrag, den Beweis, dass das Graphisomorphismus- Problem nicht vollständig istNP , und durch die Tatsache, dass ein Hauptkandidat für Zwischenprobleme ist (weder vollständig noch für ), interessiere ich mich für bekannte Beweise dass nicht in .GINPNPPGIP

Ein solcher Beweis ist die Vollständigkeit eines eingeschränkten Graph-Automorphismus-Problems (das Problem des fixpunktfreien Graph-Automorphismus ist vollständig). Dieses Problem und andere Verallgemeinerungen des wurden in " Some NP-complete problems similar to Graph Isomorphism " von Lubiw untersucht. Einige mögen als Beweis dafür argumentieren, dass trotz mehr als 45 Jahren niemand einen Polynom-Zeit-Algorithmus für .NPNPGIGI

Welche anderen Beweise müssen wir glauben, dass nicht in ?GIP

Mohammad Al-Turkistany
quelle
2
Der Subgraph-Isomorphismus ist auch NP-vollständig.
1
Ein wenig schwacher Beweis ist die wachsende Klasse von Problemen, die logspace-äquivalent zu GI sind, von denen jedoch keine offensichtliche Polyzeit-Algorithmen zu haben scheint. (Natürlich, wenn einer von ihnen einen Polytime-Algorithmus hat, dann haben sie alle.)
András Salamon
Indizien ähnlich wie bei P vs NP: Jahrzehntelange Optimierung von GI-Algorithmen, z. B. Nauty , die noch experimentell überprüfbare Nicht-P-Worst-Case-Trends aufweisen, anscheinend hauptsächlich auf zufälligen regulären Graphen.
vzn
1
Siehe auch harte Grafiken für GI-Tests
vzn
Was denkst du darüber? dharwadker.org/tevet/isomorphism
Anna Tomskova

Antworten:

11

Vor dieser Frage war ich der Meinung, dass der Graphisomorphismus in P enthalten sein könnte, dh dass es keine Beweise dafür gibt, dass GI nicht in P enthalten ist. Ich fragte mich, was für mich als Beweis gelten würde: Wenn es ausgereifte Algorithmen für - gäbe. Gruppenisomorphismus, der die verfügbare Struktur von p- Gruppen voll ausnutzt und dennoch keine Hoffnung auf eine polynomielle Laufzeit hat. Dann würde ich zustimmen, dass GI wahrscheinlich nicht in P enthalten ist. Es gibt bekannte Algorithmen, die die verfügbare Struktur ausnutzen, wie Isomorphism testing for p - Gruppen. von O'Brien (1994)pppIch habe es jedoch nicht ausführlich genug gelesen, um beurteilen zu können, ob es die verfügbare Struktur vollständig ausnutzt oder ob Hoffnung besteht, diesen Algorithmus zu verbessern (ohne die zusätzliche nicht offensichtliche Struktur von Gruppen auszunutzen ), um eine polynomielle Laufzeit zu erzielen.p

Ich wusste jedoch, dass Dick Lipton Ende 2011 Maßnahmen forderte, um die rechnerische Komplexität des Gruppen-Isomorphismus-Problems im Allgemeinen und des Gruppen-Isomorphismus-Problems im Speziellen zu klären . Also habe ich gegoogeltp

site:https://rjlipton.wordpress.com group isomorphism

um zu sehen, ob der Aufruf zum Handeln erfolgreich war. Es war in der Tat:

  1. Das Gruppenisomorphismus-Problem: Ein mögliches Polymath-Problem?
  2. Fortschritte beim Gruppenisomorphismus
  3. Drei aus CCC: Fortschritte beim Gruppenisomorphismus

Der letzte Beitrag bespricht ein Papier, das eine Laufzeit von für bestimmte wichtige Gruppenfamilien erreicht, einen Großteil der verfügbaren Struktur ausnutzt und das oben erwähnte Papier aus dem Jahr 1994 anerkennt. Da die Laufzeit von n O ( log log n ) gebunden ist ist sowohl mit der Erfahrung vereinbar, dass der Graphisomorphismus in der Praxis nicht schwierig ist, als auch mit der Erfahrung, dass niemand in der Lage ist, einen polynomialen Zeitalgorithmus zu entwickeln (auch für den Gruppenisomorphismus), kann dies als Beweis dafür gewertet werden, dass der GI nicht in P enthalten ist .nO(loglogn)nO(loglogn)

Thomas Klimpel
quelle
rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems tauchte auch bei meiner Suche auf. Er zitiert Theorem 2 Graphisomorphie in ist . Darüber hinaus gehört jedes Versprechungsproblem in S Z K zu B P P M C S P, wie es für Versprechungsprobleme definiert ist. RPMCSPSZKBPPMCSPDies ist ein Beweis dafür, dass GI nicht NP-vollständig ist, aber das war hier nicht die Frage. Lassen Sie mich hinzufügen, dass ich keine Probleme mit der Länge oder dem Stil meiner Antwort sehe, da ich eine Beweisanforderung als Aufforderung zur Abgabe einer mit Gründen versehenen Stellungnahme interpretiere.
Thomas Klimpel
5
Ich folge deiner Argumentation nicht. Woher wissen Sie, dass die "verfügbare Struktur" "voll ausgenutzt" ist? Wenn überhaupt, schlägt das Grochow-Qiao-Papier nicht vor, dass mit Kohomologie-Kursen noch viel mehr getan werden kann?
Sasho Nikolov
@SashoNikolov Mit der "verfügbaren Struktur" meine ich das Wissen über die Struktur in der gruppentheoretischen Gemeinschaft, verwandten Gemeinschaften und bestehenden Veröffentlichungen. Beispiele, bei denen die Struktur nicht "voll ausgenutzt" wird, sind Veröffentlichungen, deren Hauptziel es ist, einen praktisch umsetzbaren Algorithmus zu entwickeln, der daher irgendwann aufhört und nur die verbleibenden Einschränkungen erwähnt, ohne dass klar angegeben ist, ob diese grundlegend sind. Das Grochow-Qiao-Papier untersuchte diese und griff direkt die Komplexität der Berechnung des Gruppenisomorphismus an, daher liefern seine Ergebnisse gute Beweise.
Thomas Klimpel
11

Die kleinste Menge von Permutationen, die Sie überprüfen müssen, um sicherzustellen, dass in einer Black-Box-Einstellung keine nicht-trivialen Permutationen vorhanden sind, ist besser als aber immer noch exponentiell, OEIS A186202 .n!

Die Anzahl von Bits erforderlich , um ein nicht - markierten Graphen zu speichern von ( nlog2. Siehe Naor, Moni. "Prägnante Darstellung allgemeiner unbeschrifteter Diagramme." Discrete Applied Mathematics 28.3 (1990): 303 & ndash; 307. Der Nachweis der Komprimierungsmethode ist, wenn ich mich recht entsinne, etwas sauberer. Wie auch immer, kann Anruf,eingestelltU. Es seiL=2 ( n(n2)nlog(n)+O(n)U für beschriftete Diagramme.L=2(n2)

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

und B o o l L L , wenn Sie Exponentialgrößen konvertieren. Es ist einfacher, nur die Typensignaturen zu überprüfen, um Diagramme in kanonischer Form darzustellen, aber wie oben gezeigt, macht GC GI einfach.ULBoolLL

Chad Brewbaker
quelle
Vielen Dank. Wie stark ist diese Art von Argumenten?
Mohammad Al-Turkistany
Gibt es einen Hinweis, der diesen Zusammenhang weiter dokumentiert?
vzn
3
@ MohammadAl-Turkistany: Dies ist im Grunde ein Argument für die Komplexität von Abfragen. Aber bekannte Algorithmen, zB Babai-Luks 1983, haben diese Grenze bereits übertroffen, denke ich mit einem beachtlichen Abstand (so etwas wie gegen 2 √)2n ). 2n
Joshua Grochow
1
@ChadBrewbaker: Wenn Ihr Anliegen verschlüsselt wird und die Komplexität im Durchschnitt der Fälle hoch ist, ist nauty mit Sicherheit deutlich besser als Ihr Algorithmus. (Beachten Sie, dass die beste untere auf nauty gebunden bekannt ist (Miyazaki 1996) und ein Poly-Algorithmus wurde für die Miyazaki Graphen gefunden. Eine einfache Analyse zeigt eine untere Grenze von ( 3 / 2 ) n auf Ihrem Algorithmus.) Auch GI ist im Durchschnitt lineare Zeit (Babai-Kucera). Ω(2n/20)(3/2)n
Joshua Grochow
2
@ MohammadAl-Turkistany: Diese Frage hat mich dazu gebracht, tiefer über meine Überzeugungen zur Komplexität von GI nachzudenken. Betreff: Ihre andere Frage, beachten Sie, dass, wenn es keine Poly-Time-Turing-Reduktion (oder sogar eine Multi-Time-Turing-Reduktion) von GI zu GA gibt, P NP ist.
Joshua Grochow
8

Kozen in seiner Arbeit, Ein Cliquenproblem, das dem Graphisomorphismus äquivalent ist , gibt einen Beweis dafür, dass nicht in P ist . Folgendes stammt aus dem Papier:GIP

"Dennoch ist es wahrscheinlich, dass das Auffinden eines Polynomzeitalgorithmus für den Graphisomorphismus genauso schwierig ist wie das Auffinden eines Polynomzeitalgorithmus für ein NP-vollständiges Problem. Zur Unterstützung dieser Behauptung geben wir ein Problem an, das dem Graphisomorphismus, einer kleinen Störung, äquivalent ist davon ist NP-vollständig. "

Auch Babai spricht in seinem kürzlich erschienenen Durchbruchartikel Graph Isomorphism in quasipolynomial time gegen die Existenz effizienter Algorithmen für GI. Er stellt fest, dass das (auf GI reduzierbare) Gruppenisomorphismusproblem ein Haupthindernis für die Platzierung von GI in . Das Gruppenisomorphismusproblem (Gruppen sind durch ihre Cayley-Tabelle angegeben) ist in n O ( log n ) lösbar und es ist nicht bekannt, dass es in P ist .PnO(logn)P

Hier ist ein Auszug aus Babais Papier:

Das Ergebnis der vorliegenden Arbeit verstärkt die Bedeutung des Gruppenisomorphismusproblems (und des angegebenen Herausforderungsproblems) als Hindernis für die Platzierung des GI in P. Es ist durchaus möglich, dass der Zwischenstatus des GI (weder NP-vollständig noch polynomiell) wird bestehen bleiben.

Mohammad Al-Turkistany
quelle
2
Aus Kozens Lem. In 3 kann man ein einfacheres Beispiel für dieses Phänomen finden: Nämlich, der induzierte Subgraph-Isomorphismus (ist ein induzierter Subgraph von G ) ist genau GI, wenn | G | = | H | , ist aber NP-schwer, wenn | G | = c | H | für jedes c > 1HG|G|=|H||G|=c|H|c>1. Für diskrete Parameter wissen wir, dass es Probleme in P gibt, die schnell NP-vollständig werden (z. B. 2SAT vs 3SAT). Wissen Sie, ob es in P Beispiele für Probleme mit einigen stetigen Parametern gibt, die bei einer scharfen Schwelle NP-vollständig werden? Wenn ja, dann wäre diese Art von Argumentation kein großer Beweis dafür, dass GI nicht in P ist, aber ich kann mir so ein Beispiel nicht aus dem Kopf denken.
Joshua Grochow
2
@JoshuaGrochow Nein, mir sind solche Entscheidungsprobleme nicht bekannt. Aber für Optimierungsprobleme Ich weiß , dass eine Zuordnung der Suche nach Befriedigung der Klauseln in ist P , während eine Zuordnung der Suche nach Befriedigung 7 / 8 + ε der Klauseln ist N P -hard auch für erfüllbar 3SAT Formeln ( ε > 0 ). 7/8P7/8+ϵNPϵ>0
Mohammad Al-Turkistany
Hoppla, Klimpels Antwort enthält bereits Beweise für den Gruppenisomorphismus. Wie auch immer, es ist nützlich, Babais Perspektive in dieser Angelegenheit zu haben.
Mohammad Al-Turkistany
Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.
Raphael
5

Hier sind andere Ergebnisse noch nicht zitiert

  • Zur Härte des Graphisomorphismus / Torán FOCS 2000 und SIAM J. Comput. 33, 5 1093 & ndash; 1108.

    Wir zeigen, dass das Graph-Isomorphismus-Problem unter DLOGTIME-einheitlichen AC 0 -Reduktionen für die Komplexitätsklassen NL, PL (probabilistischer logarithmischer Raum) für jede logarithmische Raum-Modulklasse Mod k L und für die Klasse DET von Problemen NC 1, die auf reduziert werden können, schwierig ist die Determinante. Dies sind die stärksten bekannten Härteergebnisse für das Graphisomorphismusproblem und implizieren eine zufällige logarithmische Raumverringerung vom perfekten Anpassungsproblem zum Graphisomorphismus. Wir untersuchen auch Härteergebnisse für das Graph-Automorphismus-Problem.

  • Der Graph-Isomorphismus ist nicht AC 0 -reduzierbar auf Gruppen-Isomorphismus / Chattopadhyay, Toran, Wagner

    Wir geben eine neue Obergrenze für die Gruppen- und Quasigroup-Isomorphismusprobleme an, wenn die Eingabestrukturen explizit durch Multiplikationstabellen angegeben werden. Wir zeigen, dass diese Probleme durch nichtdeterministische Schaltkreise mit Polynomgröße und unbegrenztem Fan-In mit O (log log n) Tiefe und O (log 2 n) nichtdeterministischen Bits berechnet werden können, wobei n die Anzahl der Gruppenelemente ist. Dies verbessert die bestehende Obergrenze von [Wol94] für die Probleme. In der vorherigen oberen Schranke haben die Schaltungen das Fanin begrenzt, aber die Tiefe 0 (log 2 n) und auch 0 (log 2 n) nicht deterministische Bits. Wir beweisen dann, dass die Art der Schaltkreise aus unserer oberen Schranke die Paritätsfunktion nicht berechnen kann. Da Parität ist AC 0Reduzierbar auf den Graphisomorphismus bedeutet dies, dass der Graphisomorphismus unter der durch AC 0 -Reduktionen definierten Reihenfolge strikt härter ist als der Gruppen- oder Quasigruppenisomorphismus .

vzn
quelle
4
AC0
Bezüglich der "stärksten bekannten unteren Schranken für GI" ist ofc GI in NP, so dass ein tatsächlicher Beweis, dass GI nicht in P ist, äquivalent zu P ≠ NP ist! (möglicherweise über NPI ≠ ≠) ...
vzn
4
Ja, aber zum Beispiel wäre es schön zu wissen, dass GI P-schwer ist! (Natürlich hat P-Härte sehr wenig damit zu tun zu zeigen, dass etwas nicht in P ist, aber es würde zumindest darauf hindeuten, dass GI nicht in NC ist!)
Joshua Grochow