Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)

12

Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez Jamiego Smitha. W obu tych artykułach wykorzystują ideę spójnej konfiguracji (schematów) i alternatywnego, ale równoważnego sformułowania algebry komórkowej (subalgebra macierzowa indeksowana zestawem skończonym - zestaw wierzchołków zamkniętych pod zwielokrotnieniem punktowym, transpozycja złożonej sprzężonej i zawierająca Macierz tożsamości I i macierz „ wszystko jedno”J ) odpowiednio w celu zapewnienia niezbędnych kontrargumentów.

Bardzo trudno jest mi podążać za tymi argumentami i nawet jeśli niejasno podążam za poszczególnymi argumentami, nie rozumiem głównej idei. Chciałbym wiedzieć, czy istotę argumentów można wyjaśnić ogólnymi terminami - może to kosztować niewielką rygor - bez użycia języka teorii schematów lub algebry komórkowej.

DurgaDatta
źródło

Odpowiedzi:

4

Możesz zrobić znacznie więcej niż sprawdzanie wszystkich n! permutacje podczas brutalnego wymuszania rozwiązania, http://oeis.org/A186202 Graal pokazuje, że nie da się zrobić nic lepszego, lub wykorzystuje fakt, że większość grafów nie ma w nich symetrii i wykorzystuje to do obliczania prędkości.

Chad Brewbaker
źródło
2
S.S.nS.S.nS.n
1
Jeśli przetestujesz jedną nietrywialną permutację z każdego pierwszego cyklu, sprawdziłeś każdą możliwą podgrupę Sn. Nadal jest ogromny. Ponadto służy do sprawdzania automorfizmu grafów, który jest „łatwiejszy” niż izomorfizm.
Chad Brewbaker