CoNP-Zertifikat für Graph Isomorphism

Es ist leicht zu erkennen, dass der Graphisomorphismus (GI) in NP vorliegt. Es ist ein großes offenes Problem, ob GI in coNP ist. Gibt es potenzielle Kandidaten für Eigenschaften von Graphen, die als coNP-Zertifikate von GI verwendet werden können? Irgendwelche Vermutungen, die implizieren ? Was sind einige Implikationen von G I ∈ c o N P ?$GI \in coNP$$GI \in coNP$

Wenn in ist c o N P , dann hätten wir das Ergebnis: G I nicht ist N P -komplette es sei denn , N P = c o N P = P H . (Derzeit bekannt: G I ist nicht N P -vollständig, es sei denn Σ 2 P = Π 2 P = P H ).$GI$$coNP$$GI$$NP$$NP=coNP=PH$$GI$$NP$$\Sigma_2 P = \Pi_2 P = PH$

Da sich in c o A M befindet , würde eine Derandomisierung von c o A M ( doi link ) offensichtlich G I ∈ c o N P bedeuten, aber ich kenne keine Kandidatengrapheneigenschaften für das Setzen von G I ∈ c o N P Andernfalls. Ich freue mich jedoch auf weitere Antworten!$GI$$coAM$$coAM$$GI \in coNP$$GI \in coNP$

Interessanterweise wurde in diesem Papier zeigen sie auch , daß Nicht-Graph Isomorphie subexponentiellen Größe Proofs hat - das heißt, - es sei denn , P H = Σ 3 P . Dies ist zumindest in Richtung der Spitze der bedingt , dass zeigt G I ∈ C O N P .$GI \in co NSUBEXP$$PH = \Sigma_3 P$$GI \in coNP$

Wie steht es mit dem Bereich (dh Liste, ein Eintrag pro Kante) der effektiven Widerstände? Der effektive Widerstand einer Kante ist die Wahrscheinlichkeit, dass sich die Kante in einem zufälligen Spannbaum befindet. Wirksame Widerstände können mit Algorithmen von Spielman und Teng gefunden werden, obwohl ich nicht weiß, wie einfach es ist, sie tatsächlich zu implementieren (wenn man Experimente machen wollte).

Angenommen, wir haben zwei stark reguläre Graphen mit denselben Eigenwerten (und wir wissen, dass Eigenwerte nicht notwendigerweise zwischen nicht isomorphen Graphen unterscheiden). Wenn dann die effektiven Widerstände (dh wieder die Listen) gleich sind, können sie nicht zur Unterscheidung der Graphen verwendet werden. Aber warum sollten zwei Co-Spektralgraphen die gleiche Verteilung ihrer Kanten in zufälligen aufspannenden Bäumen haben? Gibt es einen bekannten Zusammenhang zwischen dem Graphenspektrum und den effektiven Widerständen eines Graphen? Können wir, wenn wir das Graphenspektrum kennen, die effektiven Widerstände berechnen?

Es könnte interessant sein, darauf hinzuweisen, dass, wenn GI nicht in coNP ist, P ≠ NP ist.

1) Wenn GI nicht in coNp ist, dann ist GI ≠ NGI

2) Wenn GI ≤ NGI ist, dann ist GI ≤ P

3) Wenn GI ≠ P ist, dann ist P ≠ NP

Als eine Konsequenz der folgenden Aussagen haben wir: Wenn GI nicht in coNP ist, dann ist P ≠ NP. Das gleiche gilt, wenn NGI nicht in NP ist.