Jakie są dowody, że Izomorfizm Grafów nie występuje w

Motywowane komentarzu Fortnow w sprawie mojego postu, dowód, że problemem nie jest izomorfizm grafów -Complete$NP$ G I N P N P P G I P , a fakt, że jest głównym kandydatem do -intermediate problemu (nie -Complete ani w ) Jestem zainteresowany znanych dowodów że nie jest w .$GI$$NP$$NP$$P$$GI$$P$

Jednym z takich dowodów jest kompletność ograniczonego problemu automorfizmu grafów (problem automorfizmu grafów swobodnych w punktach jest kompletny ). Ten problem i inne uogólnienia badano w „ Niektórych problemach NP-zupełnych podobnych do graficznego izomorfizmu ” Lubiw. Niektórzy mogą argumentować jako dowód na fakt, że pomimo ponad 45 lat nikt nie znalazł algorytmu wielomianowego czasu dla .N P G $NP$$NP$$GI$$GI$

Jakie jeszcze dowody musimy sądzić, że nie występuje w ?$GI$$P$

Przed tym pytaniem moja opinia była taka, że ​​wykres Izomorfizm może występować w P, tj. Że nie ma dowodów na to, że GI nie ma w P. Więc zadałem sobie pytanie, co by się dla mnie liczyło: gdyby istniały dojrzałe algorytmy dla - izomorfizm grupowy, który w pełni wykorzystał dostępną strukturę grup i nadal nie miałby nadziei na osiągnięcie wielomianowego środowiska uruchomieniowego, wtedy zgodziłbym się, że GI prawdopodobnie nie występuje w P. Znane są algorytmy wykorzystujące dostępną strukturę, takie jak testowanie izomorfizmu dla - grupy. autor: O'Brien (1994)p p$p$$p$$p$, ale nie przeczytałem go wystarczająco szczegółowo, aby ocenić, czy w pełni wykorzystuje dostępną strukturę, czy też istnieje nadzieja na ulepszenie tego algorytmu (bez wykorzystywania dodatkowej, nieoczywistej struktury grup ), aby uzyskać wielomianowe środowisko uruchomieniowe.$p$

Ale wiedziałem, że Dick Lipton wezwał do działania pod koniec 2011 r., Aby wyjaśnić złożoność obliczeniową problemu izomorfizmu grupowego w ogóle, a konkretnie problemu izomorfizmu grupy . Poszukałem Google$p$

site:https://rjlipton.wordpress.com group isomorphism

aby sprawdzić, czy wezwanie do działania zakończyło się powodzeniem. Rzeczywiście było to:

1. Grupowy problem izomorfizmu: możliwy problem polimorfii?
2. Postępy w zakresie izomorfizmu grupy
3. Three From CCC: Progress on Group Isomorphism

W ostatnim poście dokonano przeglądu artykułu, w którym osiągnięto środowisko wykonawcze dla niektórych ważnych rodzin grup, wykorzystano większość dostępnej struktury i potwierdzono wyżej wspomniany artykuł z 1994 roku. Ponieważ środowisko uruchomieniowe n O ( log log n ) jest powiązane jest zgodny z doświadczeniem, że izomorfizm grafów nie jest trudny w praktyce, oraz z doświadczeniem, że nikt nie jest w stanie wymyślić algorytmu wielomianowego czasu (nawet w przypadku izomorfizmu grupowego), można to uznać za dowód, że GI nie jest w P .$n^{O(\log \log n)}$$n^{O(\log \log n)}$

Najmniejszy zestaw permutacji, który musisz sprawdzić, aby sprawdzić, czy nie istnieją nietrywialne permutacje w ustawieniu czarnej skrzynki, jest lepszy niż ale wciąż wykładniczy, OEIS A186202 .$n!$

Liczba bitów potrzebnych do przechowywania niewyznakowanego wykresu z . Zobacz Naor, Moni. „Zwięzłe przedstawienie ogólnych nieznakowanych wykresów”. Discrete Applied Mathematics 28.3 (1990): 303-307. O ile pamiętam, dowód na kompresję jest trochę czystszy. W każdym razie, że umożliwia połączenie zestawu . Niech dla oznaczonych wykresów.$log_{2}$UL=2 (${n\choose 2}-n log(n) +O(n)$$U$$L=2^{{n\choose 2}}$

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

B o o l L $U^L$ i jeśli konwertujesz na wykładnicze. Samo sprawdzenie podpisów typów umieszczenie wykresów w formie kanonicznej wygląda łatwiej, ale jak pokazano powyżej GC ułatwia GI.$Bool^{L^{L}}$

$GI$$P$

„Niemniej jednak jest prawdopodobne, że znalezienie algorytmu wielomianowego czasu dla izomorfizmu grafowego będzie tak samo trudne, jak znalezienie algorytmu wielomianowego czasu dla problemu NP-zupełnego. Na poparcie tego twierdzenia podajemy problem równoważny z izomorfizmem grafowym, małą perturbację z tego jest NP-kompletny. ”

$P$$n^{O(\log n)}$$P$

Oto fragment artykułu Babai:

Wynik niniejszej pracy zwiększa znaczenie problemu grupowego izomorfizmu (i stwierdzonego problemu prowokacji) jako bariery dla umieszczenia GI w P. Jest całkiem możliwe, że status pośredni GI (ani NP-całkowity, ani czas wielomianowy) będzie się utrzymywać.

oto inne wyniki jeszcze nie cytowane

• O twardości Graph Isomorphism / Torán FOCS 2000 i SIAM J. Comput. 33, 5 1093–1108.

  Pokazujemy, że problem izomorfizmu grafu jest trudny przy jednolitych redukcjach DLOGTIME AC ⁰ wielokrotnych jeden dla klas złożoności NL, PL (probabilistyczna przestrzeń logarytmiczna) dla każdej klasy modułowej przestrzeni logarytmicznej Mod _kL i dla klasy DET problemów NC ¹ redukowalnych do wyznacznik. Są to najsilniejsze znane wyniki twardości dla problemu izomorfizmu grafu i implikują losową redukcję przestrzeni logarytmicznej od idealnego problemu dopasowania do izomorfizmu grafu. Badamy również wyniki twardości dla problemu automorfizmu grafów.

• Wykres Izomorfizm nie jest redukowany przez AC ⁰ do Grupowego Izomorfizmu / Chattopadhyay, Toran, Wagner

  Dajemy nową górną granicę dla problemów z izomorfizmem grupowym i quasigroup, gdy struktury wejściowe są podane jawnie przez tabliczki mnożenia. Pokazujemy, że problemy te można obliczyć za pomocą niedeterministycznych obwodów wielomianowych o nieograniczonym wachlowaniu z głębokością O (log log n) i bitami niedeterministycznymi O (log ² n), gdzie n jest liczbą elementów grupy. Poprawia to istniejącą górną granicę z [Wol94] dla problemów. W poprzedniej górnej granicy obwody ograniczały Fanin, ale głębokość O (log ² n), a także O (log ² n) bity niedeterministyczne. Następnie dowodzimy, że rodzaj obwodów z naszej górnej granicy nie może obliczyć funkcji parzystości. Ponieważ parzystość wynosi AC ⁰redukuje się do izomorfizmu grafów, oznacza to, że izomorfizm grafów jest ściśle trudniejszy niż izomorfizm grupowy lub quasigroup w kolejności określonej przez redukcje AC ⁰ .