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

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 ? $(G \leq S_n, *)$ $n$ $s \in \{0, 1\}^n$ $G.s$ $s$ $G$

permutations gr.group-theory complexity

— Samuel Schlesinger
źródło

Oczywiście, izomorfizm strunowy w sensie Babai można zredukować do tego problemu, jak podano

x, y

$x, y$ ciągi i grupa

G

$G$ moż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:

Ten problem to $FP^{NP}$ -kompletne, jak pokazano tutaj .

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

— Boson
źródło

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 gdy $G$ jest elementarną abelową grupą 2 (= każdy nietrywialny element $G$ ma zamówienie 2).

— Joshua Grochow
źródło