Dowody, że problemem nie jest izomorfizm grafów

Problem z izomorfizmem grafów jest jednym z najdłużej utrzymujących się problemów, które opierały się klasyfikacji do problemów kompletnych lub N P. Mamy dowody, że to nie może być N P -Complete. Po pierwsze, wykres Izomorfizm nie może być N P -Complete chyba że wielomian hierarchii [1] opada do drugiego poziomu. Także liczenie [2] wersja GI jest wielomian czasie Turinga odpowiednikiem wersji decyzji, która nie posiada jakiegokolwiek znanego N P -Complete problemu. Wersja liczenie N P problemów -Complete wydaje się mieć znacznie większą złożoność. Na koniec wynik słabości [3] GI w odniesieniu do P P ($P$$NP$$NP$$NP$$NP$$NP$$PP$ ) nie jest znany z utrzymywania jakiegokolwiekproblemu N- p . Zmniejszony wynik GI został poprawiony do S P P G I = S P P po tym, jak Arvind i Kurur udowodnili, że GI jest w S P P [4].$PP^{GI}=PP$$NP$$SPP^{GI}=SPP$$SPP$

Jakie inne (najnowsze) wyniki mogą dostarczyć dalszych dowodów, że GI nie może być -Complete?$NP$

Zadałem pytanie na Mathoverflow bez odpowiedzi.

[1]: Uwe Schöning, „Graf izomorfizm ma niską hierarchię”, Materiały z 4. dorocznego sympozjum na temat teoretycznych aspektów informatyki, 1987, 114–124

[2]: R. Mathon, „Notatka na temat problemu liczenia izomorfizmów na wykresie”, Information Processing Letters, 8 (1979) s. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), „Wykres izomorfizm jest niski dla PP”, Złożoność obliczeniowa 2 (4): 301–330

[4]: V. Arvind i P. Kurur. Wykres izomorfizm jest w SPP, ECCC TR02-037, 2002.

Z powodu ostatniego wyniku Babai (patrz artykuł ) jest w czasie quasi-wielomianowym ( Q P ). Jeśli G I to N P -Complete, to oznacza N P ⊆ P P = D T I M E ( N p O L y l O $GI$$QP$$GI$$NP$. To z kolei implikujeEXP=NEXP, patrz tutaj. Dlatego też, jeśli powszechnie akceptowane przypuszczenieEXP≠NEXPposiada, aG, żenie może byćNP-Complete.$NP\subseteq QP=DTIME(n^{polylog\, n})$$EXP=NEXP$$EXP\neq NEXP$$GI$$NP$