Pytania otagowane jako graph-isomorphism

Dwa wykresy G, H są izomorficzne, jeśli istnieje znakowanie wierzchołków G, które wytwarza H, i odwrotnie. Graficzny problem izomorfizmu (GI) ma decydować, czy dwa podane są izomorficzne. Oprócz praktycznego zainteresowania, Karp w 1972 r. Stwierdził, że ma nieznaną złożoność, jest jednym z niewielu naturalnych kandydatów na problem pośredni NP i doprowadził do powstania klasy złożoności AM.

1
Jak cytować nowy wynik izomorfizmu grafu Babai?
Niedawno Babai opublikował artykuł na temat STOC 2016, twierdząc, że izomorfizm grafów można rozwiązać w czasie quasipolynomialnym. Na początku 2017 r. Babai wycofał roszczenie quasipolomomial z powodu poważnych błędów wykrytych przez Haralda Helfgotta. Jak wyjaśnił sam Babai, ta wada sprawia, że ​​poprawa jest bardziej skromna pod względem czasu działania. Około …
1
Kontrprzykład efektywnego algorytmu Corneila dla izomorfizmu grafów
W pracy „Efficient Al Algorytm for Graph Isomorphism” autorstwa Corneila i Gotlieba, 1970, stwierdzono hipotezę, na której opierał się algorytm rozwiązywania GI w czasie wielomianowym. Mianowicie: że reprezentatywne wykresy wykazują podział automorfizmu na dany wykres Oczywiście, ta hipoteza nie została do tej pory udowodniona (w przeciwnym razie wiedzielibyśmy, że GI …
2
podobne matryce
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że są permutacją, które wiążą ten problem z …
1
Twardość NP problemu podziału grafu?
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i .EEEE1E1E_1E2E2E_2V1V1V_1V2V2V_2E1∪E2=EE1∪E2=EE1∪E2=EV1∪V2=VV1∪V2=VV1∪V2=V Ten problem jest co najmniej tak trudny jak problem z …
2
Twarde instancje do testowania izomorfizmu grafów
Czy przypadek bardzo regularnych grafów jest najtrudniejszy do testowania GI? gdzie „najtrudniejszy” jest używany w pewnym sensie „zdrowego rozsądku” lub „średnio”, że tak powiem. Wolfram MathWorld wspomina o niektórych „patologicznie trudnych grafach”. Czym oni są? Mój przykładowy zestaw 25 par wykresów: http://funkybee.narod.ru/graphs.htm Testowałem wiele innych, ale wszystkie tego samego rodzaju …
2
Podejścia do GI inspirowane problemem węzłów
Zarówno GI, jak i Knot Problem stanowią problem decydowania o równoważności strukturalnej obiektów matematycznych. Czy są jakieś wyniki ustanawiające powiązania między nimi? Ładne powiązania problemu węzłów z fizyką statystyczną zostały zbadane za pomocą wielomianów węzłów , czy istnieją podobne wyniki dla ?G IsoljaGI Byłoby to szczególnie pomocne, aby wiedzieć, czy …
1
Generowanie wykresów za pomocą trywialnych automorfizmów
Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym. Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu). W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy …
2
Czy algorytm quasiipolomialnego czasu Babai faktycznie generuje izomorfizm?
Mam (mam nadzieję, że proste, może głupie) pytanie na przełomowy artykuł Babai, który pokazuje, że jest quasipolynomial.GIGI\mathsf{GI} Babai pokazał, jak stworzyć certyfikat, że dwa wykresy dla są izomorficzne, z czasem quasipolynomial in.i ∈ { 1 , 2 } v = | V i |Gi=(Vi,Ei)Gi=(Vi,Ei)G_i=(V_i,E_i)i∈{1,2}i∈{1,2}i\in\{1,2\}v=|Vi|v=|Vi|v=|V_i| Czy Babai rzeczywiście pokazać , jak …
1
Testowanie izomorfizmu grafów asymetrycznych
Czytając pytanie Przykłady gdzie wyjątkowość rozwiązania sprawia, że łatwiej znaleźć , nowy (? Łatwiej) pytanie przyszło mi do głowy: Właściwie nie wiemy, czy izomorfizm grafów ( ) problem jest w P .GIGIGIPPP Ale co się stanie, jeśli założymy, że zarówno i G 2 są asymetryczne (tj. Oba mają jedynie trywialny …
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.