Złożoność problemów związanych z permutacją

Biorąc pod uwagę grupę permutacji na i dwa wektory gdzie jest skończonym alfabetem, co nie jest tu całkiem istotne, pytanie brzmi, czy istnieje jakieś taki, że gdzie oznacza zastosowanie permutacji na w oczekiwany sposób. $G$ $[n]=\{1, \cdots, n\}$ $u,v\in \Gamma^n$ $\Gamma$ $\pi\in G$ $\pi(u)=v$ $\pi(u)$ $\pi$ $u$

Załóżmy ponadto, że jest dane wejściowe przez skończony zbiór generatorów. Jaka jest złożoność problemu? W szczególności, czy jest to w NP? $G$ $S$

cc.complexity-theory graph-isomorphism permutations użytkownik27313
źródło

Co rozumiesz przez skończony zestaw generatorów? Jak to jest reprezentowane w danych wejściowych?

Myślę, że przykładem jest: dwa generatory

to grupa generowana przez

S_{1} = (12) (3)

$S_1=(1 2)(3)$

S_{2} = (13) (2)

$S_2=(1 3)(2)$

G

$G$

S_{1}

$S_1$

S_{2}

$S_2$

maomao

Ogólnie rzecz biorąc, problem ten byłby trudny do przeprowadzenia (prawdopodobnie został już to zbadany w niektórych dokumentach, o których nie wiem). Niemniej jednak inne rozwiązanie problemu (związane również z grą w sudoku) może Cię zainteresować

Nikos M.

Co więcej, jest to odwrotny problem (do którego można podejść w MAKSYMALNY sposób a-la Jaynes)

Nikos M.

Pytanie nie brzmi, czy jest to NP-trudne, ale czy jest w NP. Trywialna górna granica to tylko PSPACE.

Emil Jeřábek

Odpowiedzi:

$g_1, \ldots, g_k, g \in S_n$ $S_n$ $n$ $g \in \langle g_1, \ldots, g_k \rangle$ $\text{NC} \subseteq \text{P}$ $u, v \in \Gamma^n$ $g \in S_n$ $g \in G$ $g(u) = v$ $\text{NP}$

Aby uzupełnić tę odpowiedź:

$\text{P}$ $\text{NC}^3$ $\text{NC}$ $\text{AC}^0$ $\text{P}$ $\text{NP}$ $\text{PSPACE}$ (i ukończ dla tej klasy z nielicznymi wyjątkami).

$19^\text{th}$

Michael Blondin
źródło

Moja odpowiedź była niepoprawna i usunąłem ją (podgrupa, którą w odpowiedzi oznaczałem jako N, nie była w ogóle normalna). Myślę, że problem jest w P (i prawdopodobnie także w NC), ale nie mam obecnie dowodu.

Tsuyoshi Ito,

π

$\pi$

Można łatwo zbudować jeden wybór dla π, ale co powinniśmy zrobić, jeśli ten π nie należy do G? Prawdopodobnie istnieje sposób na znalezienie właściwej wartości π od początku, ale w tej chwili nie wiem, jak to zrobić.

Tsuyoshi Ito,

Masz rację. Przeredaguję moją odpowiedź z powrotem do górnej granicy NP.

Michael Blondin,

Dziękuję za edycję i przepraszam, że spowodowałem zamieszanie z powodu mojej błędnej odpowiedzi.

Tsuyoshi Ito,

$\Gamma$ $G$ $\mathsf{NP} \cap \mathsf{coAM}$

Redukcja z GI: niech i niech będzie indukowaną akcją na parach. $N = \binom{n}{2}$ $G \leq S_N$ $S_n$

$\mathsf{coAM}$ Protokół : Arthur losowo wybiera element (nie jestem pewien, czy da się to zrobić dokładnie jednakowo, ale myślę, że znane algorytmy są wystarczająco zbliżone do ujednolicenia dla tego wyniku) i stosuje go zarówno jak i . Z prawdopodobieństwem 1/2 zamienia i , a następnie przedstawia je Merlinowi i pyta, który był który. $G$ $u$ $v$ $u$ $v$

Joshua Grochow
źródło

Łącząc mój komentarz do odpowiedzi Michaela Blondina z twoją odpowiedzią, teraz obawiam się, że przypadkowo postanowiłem pomyśleć, że GI jest w P (i prawdopodobnie również w NC).

Tsuyoshi Ito,