Gibt es eine Ergebnisart mit Lückenverstärkung für das Graph-Isomorphismus-Problem?

53

Angenommen, und G 2 sind zwei ungerichtete Graphen in der Scheitelmenge { 1 , … , n } . Die Graphen sind dann und nur dann isomorph, wenn es eine Permutation Π gibt, so dass G 1 = Π ( G 2 ) , oder formal, wenn es eine Permutation Π gibt, so dass ( i , j ) genau dann eine Kante in G 1 ist wenn ( Π ( i ) , Π ( jG1G2{1,…,n}ΠG1=Π(G2)Π(i,j)G1 ist eine Kante in G 2 . Das Graphisomorphismusproblem ist das Problem der Entscheidung, ob zwei gegebene Graphen isomorph sind.(Π(i),Π(j))G2

Gibt es eine Operation für Graphen, die eine "Gap Amplification" im Stil von Dinurs Beweis des PCP-Theorems erzeugt ? Mit anderen Worten, gibt es eine Polynomzeit berechenbare Transformation von nach ( G ' 1 , G ' 2 ), so dass(G1,G2)(G1′,G2′)

  • wenn und G 2 isomorph sind, dann sind G ' 1 und G ' 2 auch isomorph, undG1G2G1′G2′
  • wenn und G 2 nicht isomorph sind, dann ist für jede Permutation Π der Graph G ' 1 " ϵ -far" von Π ( G ' 2 ) für eine kleine Konstante ϵ , wobei ϵ -far bedeutet, dass wenn wir wählen ( i , j ) gleichmäßig zufällig, dann mit einer Wahrscheinlichkeit von ε entweder G1G2ΠG1′ϵΠ(G2′)ϵϵ(i,j)ϵ
    • ist eine Kante von G ' 1 und ( Π ( i ) , Π ( j ) ) ist keine Kante von G ' 2 , oder(i,j)G1′(Π(i),Π(j))G2′
    • ist keine Kante von G ' 1 und ( Π ( i ) , Π ( j ) ) ist eine Kante von G ' 2 .(i,j)G1′(Π(i),Π(j))G2′
cc.complexity-theory graph-isomorphism pcp Andre Chailloux
quelle
5
@domotorp: "Polynom-Zeit-Transformation" ist eine Standardterminologie, die sich auf eine deterministische Polynom-Zeit-Turing-Maschine bezieht, deren Eingabe und Ausgabe beide Zeichenfolgen sind. In diesem Fall nimmt diese Turingmaschine das Paar (G1, G2) als Eingabe und erzeugt das Paar (G'1, G'2) als Ausgabe. Jeder Graph wird beispielsweise als benachbarte Matrix codiert.
Tsuyoshi Ito
1
Ich dachte, das PCP-Theorem sei für alle NP-Probleme gültig, also sollte es insbesondere für den Graphisomorphismus gelten?
Denis
2
@dkuper Der Autor möchte fragen, ob es eine lückenverstärkende Reduktion gibt, die Instanzen von Graphisomorphismus auf Instanzen von Graphisomorphismus mit einer größeren Lücke reduziert. er fragt nicht direkt nach dem PCP-Theorem, sondern nur nach einer Technik, mit der die Härte der Approximation bewiesen werden kann ...
argentpepper
3
Wahrscheinlich ein langer Versuch, aber könnten Sie zeigen, dass Sie, wenn dies der Fall wäre, den Graphisomorphismus in der Quantenpolynomzeit lösen könnten?
Neal Young
3
Es entspricht dem gegenwärtigen Wissensstand, dass sogar SAT einen linearen Zeitalgorithmus hat, so dass es unwahrscheinlich ist, dass das, was Sie geschrieben haben, bekannt ist. Wenn ja, fügen Sie bitte einen Verweis auf Ihre Antwort hinzu.
Kaveh

Antworten:

2

Ich weiß nicht, ob so etwas existieren könnte oder nicht. Es ist jedoch interessant (und vielleicht zum richtigen Zeitpunkt) festzustellen, dass eine solche "Gap Amplification" wahrscheinlich einen quasipolynomialen Zeitalgorithmus für den Graph-Isomorphismus implizieren würde (anders als der kürzlich angekündigte).

In diesem Artikel wird ein Näherungsalgorithmus für das "MAX-PGI" -Problem der Maximierung von übereinstimmenden Kanten- / Nichtkantenpaaren angegeben. Wenn wir von GI auf "Gap-MAX-PGI" reduzieren, können wir näherungsweise unterscheiden, auf welcher Seite der Lücke wir uns befinden.

Ich denke also, dass Dinurs Beweis des PCP-Theorems angesichts der Hürden, die überwunden werden müssten, wahrscheinlich nicht direkt auf einen solchen "Gap Amplifier" verallgemeinerbar ist.

Joe Bebel
quelle