Złożoność obliczania leksykograficznie minimalnego elementu orbity

9

Biorąc pod uwagę silne generatory dla grupy działającej na ciągach bitów o długości i elemencie , jak trudno jest obliczyć leksykograficznie minimalny element , orbity w ?(sol≤S.n,∗)ns∈{0,1}nsol.sssol

permutations gr.group-theory complexity Samuel Schlesinger
źródło
1
Oczywiście, izomorfizm strunowy w sensie Babai można zredukować do tego problemu, jak podano x,y ciągi i grupa solmożemy po prostu znaleźć ich minimalnych przedstawicieli na orbicie jak powyżej i bezpośrednio je porównać, ale nie jest jasne, że jeśli izomorfizm strun jest łatwy, to jest to łatwe. Zobaczę, czy praca Babai wskazuje, jak to zrobić.
Samuel Schlesinger
Artykuł Babai nie zajmuje się tym pytaniem; na str. 11 wyraźnie mówi, że papier nie zajmuje się kwestią normalnych form. Nie oznacza to, że techniki te nie mogą być przydatne do znalezienia normalnej formy, tylko że byłoby to niebanalnym wkładem.
Joshua Grochow
Dziękuję @JoshuaGrochow Nie jestem pewien, czy mam doświadczenie w stosowaniu tych technik, ale zobaczę, co da się zrobić. Jest odpowiednio trudny, nawet jeśli jest quasipolomial, że nie jest już dla mnie przydatny w sposób, w jaki chciałem go używać.
Samuel Schlesinger
Jeśli jesteś zainteresowany konkretnymi rozwiązaniami tego problemu, polecam przyjrzeć się publikacjom T. Junttili (którego cytuję w mojej odpowiedzi), szczególnie jego pracy doktorskiej i jego pracy nad izomorfizmem grafowym i ogólnie symetriami.
Boson

Odpowiedzi:

5

Ten problem to faP.N.P.-kompletne, jak pokazano tutaj .

Oznacza to, że lider leksykograficzny orbity jest zbudowany w deterministycznym wielomianowym czasie z dostępem do N.P.-wyrocznia.

Boson
źródło
5

Ten problem jest trudny NP.

Chociaż może być możliwe znalezienie jakiejś kanonicznej postaci izomorfizmu struny, powiedzmy, w czasie quasi-poli, bez zakłócania naszych obecnych domysłów, jak wygląda świat złożoności, znalezienie leksykograficznie najmniejszego łańcucha izomorficznego jest trudne. To jest dokładnie treść Propozycji 3.1 tutaj . W rzeczywistości pokazują, że pozostaje trudny do NP, nawet gdysol jest elementarną abelową grupą 2 (= każdy nietrywialny element sol ma zamówienie 2).

Joshua Grochow
źródło