Wie hoch ist die derzeit bekannte Härte des Graphisomorphismus?

21

Inspiriert von der Frage, ob Factoring als P-hart bekannt ist , frage ich mich, wie der derzeitige ähnliche Wissensstand die Härte des Graph-Isomorphismus betrifft. Ich bin sicher, dass derzeit nicht bekannt ist, ob GI in P ist, aber:

Was ist die derzeit bekannteste größte Klasse, die GI schwerer ist als?

(es wurde bei einer ähnlich klingenden Frage nicht beantwortet )

Um auf einige der Kommentare einzugehen, möchte ich die derzeit bekannten maximalen Klassen kennen, für die das Problem vollständig ist. Bekannte Algorithmen für GI sind durch Superpolynomfunktionen begrenzt, und es ist ein Mitglied von NP. Es ist jedoch nicht bekannt, dass GI P-hart ist. Ich würde gerne die Klassen C kennen, für die es bekanntermaßen C-schwer und hoffentlich so umfassend wie möglich ist.

Mitch
quelle
2
"es wurde bei einer ähnlich klingenden frage nicht beantwortet" Wirklich? Ich denke, die Antwort von Joshua Grochow hier beantwortet die Frage.
Tyson Williams
Schauen Sie sich den Abschnitt "Complexity Class GI" hier an: en.wikipedia.org/wiki/Graph_isomorphism_problem
Aaron Sterling
3
@Tyson und wer auch immer sein Kommentar hochgestuft hat: Ich denke, Mitch sagt, dass die Antwort dort nur obere Grenzen für den Graph-Isomorphismus gibt, nicht für die Härte des Graph-Isomorphismus.
Tsuyoshi Ito
Ich möchte hinzufügen, dass ich dies nicht als doppelte Frage sehe. Die Antwort von Joshua gibt obere Schranken. Diese Frage klingt eher wie: "Ist GI mindestens AC0 schwer?" - Ja, stimme @ Tsuyoshi zu.
Aaron Sterling
6
Für planare Graphen ist bekannt, dass es für L ... Siehe theorie.informatik.uni-ulm.de/Personen/toran/beatcs/…
Joshua Herman

Antworten:

22

NC1

Dies scheint das bisher stärkste Härteergebnis zu sein.

Mateus de Oliveira Oliveira
quelle
Hervorragende Referenz (und mit zusätzlicher Belastung für die Augen auf ihrer Seite, scheint ca. 2004 zu sein).
Mitch
In der Tat ist dies ein schönes Papier.
Mateus de Oliveira Oliveira