Kompleksitas masalah terkait permutasi

Diberikan grup permutasi pada [ n ] = { 1 , ⋯ , n } , dan dua vektor u , v ∈ Γ n di mana Γ adalah alfabet terbatas yang tidak cukup relevan di sini, pertanyaannya adalah apakah ada beberapa π ∈ G sedemikian rupa sehingga π ( u ) = v di mana π ( u ) berarti menerapkan permutasi π pada Anda dengan cara yang diharapkan.$G$$[n]=\{1, \cdots, n\}$$u,v\in \Gamma^n$$\Gamma$$\pi\in G$$\pi(u)=v$$\pi(u)$$\pi$$u$

Anggap lebih jauh bahwa diberikan, sebagai input, oleh himpunan S yang terbatas dari generator. Apa kerumitan masalahnya? Secara khusus, apakah itu dalam NP?$G$$S$

Misalkan mana S n adalah grup permutasi pada n elemen. Pengujian apakah g ∈ ⟨ g 1 , ... , g k ⟩ dapat dilakukan di NC ⊆ P berdasarkan [1]. Biarkan u , v ∈ Γ n , maka cukup tebak g ∈ S n , tes dalam waktu polinomial apakah g ∈ $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$dan apakah . Ini menghasilkan NP batas atas.$g(u) = v$$\text{NP}$

Untuk melengkapi jawaban ini:

Keanggotaan grup terbukti milik (Furst et al. 1980), kemudian ke NC 3 untuk kelompok abelian (McKenzie & Cook 1987; Mulmuley 1987), ke NC untuk kelompok nilpotent (Luks & McKenzie 1988), kelompok yang dapat dipecahkan (Luks & McKenzie 1988), kelompok dengan faktor komposisi non-abelian yang terbatas (Luks 1986), dan akhirnya semua kelompok (Babai et al. 1987). Klasifikasi kompleksitas serupa dari keanggotaan monoida aperiodik berutang kepada (Beaudry 1988; Beaudry et al. 1992; Kozen 1977), yang menunjukkan bahwa keanggotaan untuk setiap varietas monoid aperiodik tetap adalah dalam AC 0 , P , NP , atau $\text{P}$$\text{NC}^3$$\text{NC}$$\text{AC}^0$$\text{P}$$\text{NP}$$\text{PSPACE}$ (dan selesaikan untuk kelas itu dengan sedikit pengecualian).

[1] L. Babai, EM Luks & A. Seress. Grup permutasi di NC. Proc Simposium ACM ke tentang Teori komputasi, hal. 409-420, 1987.$19^\text{th}$

Masalah Anda dikenal sebagai ( -) string G -isomorphism. Hal ini di kelas yang cukup sempit masalah di sekitar Grafik isomorfisma: itu setidaknya sekeras GI, dan di N P ∩ c o A M .$\Gamma$$G$$\mathsf{NP} \cap \mathsf{coAM}$

Pengurangan dari GI: misalkan , dan biarkanG≤SNmenjadi aksi terinduksi dariSnpada pasangan.$N = \binom{n}{2}$$G \leq S_N$$S_n$

protokol: Arthur secara acak memilih unsur G (Saya tidak yakin ini bisa dilakukan persis seragam, tapi saya pikir algoritma yang dikenal cukup dekat untuk seragam untuk hasil ini) dan berlaku untuk kedua u dan v . Dengan probabilitas 1/2 ia menukar u dan v , lalu menyajikannya ke Merlin dan bertanya yang mana.$\mathsf{coAM}$$G$$u$$v$$u$$v$

Terlepas dari komentar saya, saya juga akan menambahkan jawaban.

Dalam kasus dua vektro yang diberikan diketahui permutasi satu sama lain (dan permutasi diketahui / diasumsikan berada dalam kelompok diberikan ). Maka permutasi yang mengubah v → u dapat ditemukan dalam waktu linier seperti:$G$$v \to u$

1. Sejajarkan 2 vektor satu di bawah yang lain

2. Permutasi ditemukan dengan mulai dari elemen pertama dari yang ditransformasikan menjadi elemen pertama dari $v$$u$

3. Dapatkan posisi elemen pada langkah sebelumnya (dari ke v ) dan ulangi langkah (2), maka itu adalah elemen ke-2 dari permutasi dan seterusnya, sampai, semua elemen dilintasi.$u$$v$

Ketika apakah kedua vektor tidak diketahui secara positif permutasi satu sama lain (atau untuk kasus yang lebih umum di mana ada beberapa transformasi, seperti misalnya permainan sudoku), periksa Masalah Solusi Lain yang pada umumnya NP-hard. Ini membutuhkan untuk menggunakan beberapa transformasi simetri (misalnya permutasi) yang memenuhi kendala dari masalah yang diberikan untuk menghasilkan solusi lain dari masalah yang diberikan solusi awal.

Lebih jauh lagi ini adalah bagian dari masalah yang dikenal sebagai Masalah Invers (a-la Jaynes)