Jaka jest obecnie znana twardość izomorfizmu grafów?


21

Zainspirowany tym pytaniem jest faktoring znany jako P-hard , zastanawiam się, jaki jest obecny podobny stan wiedzy na temat twardości izomorfizmu grafów. Jestem pewien, że obecnie nie wiadomo, czy GI jest w P, ale:

jaka jest obecnie największa klasa, w której GI jest trudniejsza?

(nie było odpowiedzi na podobne pytanie brzmiące )

Aby odpowiedzieć na niektóre komentarze, chcę poznać obecnie znane maksymalne klasy, dla których GI problem jest kompletny. Znane algorytmy dla GI są górnie ograniczone funkcjami superpolinomialnymi i należą do NP. Ale nie wiadomo, że GI jest twarde. Chciałbym poznać każdą klasę C, dla której - jest znana - jest C-trudna i, mam nadzieję, możliwie jak najbardziej inkluzywna.


2
„nie było odpowiedzi na podobne brzmiące pytanie” Naprawdę? Myślę, że odpowiedź Jozuego Grochowa odpowiada na pytanie tutaj.
Tyson Williams,

Spójrz na sekcję „GI klasy złożoności” tutaj: en.wikipedia.org/wiki/Graph_isomorphism_problem
Aaron Sterling

3
@Tyson i ktokolwiek głosował za jego komentarzem: Myślę, że Mitch mówi, że odpowiedź tam daje jedynie górne granice Izomorfizmu Grafów, a nie twardość Izomorfizmu Grafów.
Tsuyoshi Ito

Chciałbym dodać, że nie widzę w tym duplikatu pytania. Odpowiedź Jozuego określa górne granice. To pytanie brzmi bardziej: „Czy GI jest co najmniej AC0 trudne?” - tak, zgadzam się z @Tsuyoshi.
Aaron Sterling

6
W przypadku wykresów płaskich wiadomo, że jest kompletny dla L ... Zobacz theorie.informatik.uni-ulm.de/Personen/toran/beatcs/…
Joshua Herman

Odpowiedzi:


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.