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 Mamy dowody, że to nie może być -Complete. Po pierwsze, wykres Izomorfizm nie może być -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 -Complete problemu. Wersja liczenie problemów -Complete wydaje się mieć znacznie większą złożoność. Na koniec wynik słabości [3] GI w odniesieniu do ( $P$ $NP$ $NP$ $NP$ $NP$ $NP$ $PP$ ) nie jest znany z utrzymywania jakiegokolwiekproblemu . Zmniejszony wynik GI został poprawiony do po tym, jak Arvind i Kurur udowodnili, że GI jest w [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.

cc.complexity-theory graph-isomorphism

— Mohammad Al-Turkistany
źródło

Ile jeszcze dowodów potrzebujesz? Pozwól, że odwrócę pytanie: jakie są dowody, że GI nie występuje w P?

— Lance Fortnow

@LanceFortnow Myślę, że fakt, że nie mamy nawet czasu algorytm quasi-wielomian dla GI jest najlepszym dowodem, że nie ma w GI

. Czy znasz innych?

P

$P$

— Mohammad Al-Turkistany

poszlakowymi dowodami na to, że GI jest w P, jest to, że (afaik / afact) nikt nie może konstruować twardych instancji innych niż P (nawet losowo?) i nie ma nawet żadnych (przypuszczalnych) kandydatów. ps to pytanie wydaje się być bliskie aktualnej znanej twardości GI

— 2015

@vzn Jest problemem HW udowodnić, że jeżeli

, wszystkie języki w

wyjątkiem

byłoby

-Complete (to w ramach redukcji karp).

P = N P

${\sf P}={\sf NP}$

P

${\sf P}$

\emptyset

$\emptyset$

Σ^{*}

$\Sigma^*$

N P

${\sf NP}$

— Mohammad Al-Turkistany

@Arul Zobacz mój komentarz do VZN. Zasadniczo, jeśli P = NP, wówczas GI musi być NP-kompletny przy redukcji Karp.

— Mohammad Al-Turkistany

Z powodu ostatniego wyniku Babai (patrz artykuł ) jest w czasie quasi-wielomianowym ( ). Jeśli to -Complete, to oznacza $GI$ $QP$ $GI$ $NP$ . To z kolei implikuje, patrz tutaj. Dlatego też, jeśli powszechnie akceptowane przypuszczenieposiada, anie może być-Complete. $NP\subseteq QP=DTIME(n^{polylog\, n})$ $EXP=NEXP$ $EXP\neq NEXP$ $GI$ $NP$

— Andras Farago
źródło