Menentukan apa yang dapat dicapai dengan permutasi elemen-elemen dari kelompok nonkomutatif

Perbaiki kelompok terbatas . Saya tertarik pada masalah keputusan berikut: input adalah beberapa elemen dengan urutan parsial pada mereka, dan pertanyaannya adalah apakah ada permutasi dari elemen yang memenuhi pesanan dan sedemikian rupa sehingga komposisi elemen dalam order menghasilkan elemen netral grup .G $G$$G$$e$

Secara resmi, masalah -test adalah sebagai berikut, di mana grup diperbaiki:$G$$G$

• Input: a terbatas sebagian memerintahkan set dengan fungsi pelabelan dari ke .μ P $(P, <)$$\mu$$P$$G$
• Keluaran: apakah ada ekstensi linear (yaitu, total order sedemikian rupa sehingga untuk semua , menyiratkan ), sehingga, menulis elemen-elemen dari mengikuti total pesanan sebagai , kami memiliki .( P , < ′ ) x , y ∈ P x < y x < ′ y P < ′ x 1 , … , x n μ ( x 1 ) ⋅ ⋯ ⋅ μ ( x n ) = $P$$(P, <')$$x, y \in P$$x < y$$x <' y$$P$$<'$$x_1, \ldots, x_n$$\mu(x_1) \cdot \cdots \cdot \mu(x_n) = e$

Untuk grup , masalah -test jelas dalam NP. Pertanyaan saya adalah: Apakah ada grup sehingga masalah -test NP-hard?G G G$G$$G$$G$$G$

Beberapa komentar tentang pernyataan masalah yang setara:

• Bahasa poset dan ekstensi linier dapat secara ekuivalen diganti dengan bahasa DAG dan pesanan topologi. Yaitu, jika Anda mau, Anda dapat menganggap input sebagai DAG dengan simpul dilabeli dengan elemen grup, dan sebagai output yang menanyakan apakah semacam topologi dari input yang DAG capai, .$e$
• Seseorang malah bisa mempertimbangkan masalah yang lebih sulit di mana kita diberi poset dan , dan bertanya apakah (bukan ) dapat direalisasikan. Sebenarnya masalah yang lebih kuat berkurang menjadi di atas: kita dapat bertanya apakah dapat direalisasikan oleh , di mana adalah tetapi dengan elemen berlabel yang lebih kecil daripada yang lainnya. Karenanya pilihan alami dari dalam definisi di atas.g ∈ G g e e ( P ′ , < ) P ′ P g - 1$(P, <)$$g \in G$$g$$e$$e$$(P', <)$$P'$$P$$g^{-1}$$e$

Sekarang, tentang upaya saya untuk memecahkan masalah:

• Tentu saja, jika grup adalah komutatif, masalah -test jelas di PTIME karena semua ekstensi linier mencapai elemen grup yang sama, jadi kita bisa memilih salah satu dari mereka dengan jenis topologi dan memeriksa apakah itu atau tidak. Jadi kasus yang menarik adalah non-komutatif . Lebih umum, jika memiliki homomorfisme pada beberapa kelompok komutatif non-sepele (misalnya, tanda tangan , untuk permutasi), kondisi yang diperlukan tetapi tidak mencukupi adalah untuk melihat masalah melalui homomorfisme dan memeriksanya di PTIME pada gambar komutatif. . Saya gagal melihat apakah ini dapat digeneralisasi ke skema dekomposisi untuk semua grup hingga.G e G $G$$G$$e$$G$$G$
• Jika relasi urutan kosong (yaitu, kami diberi multiset elemen dalam dan dapat menggunakan permutasi apa pun), masalahnya dapat diselesaikan dengan pemrograman dinamis, di mana status adalah jumlah kemunculan setiap elemen dalam yang masih tidak digunakan (ingat bahwa sudah diperbaiki, jadi jumlah status kemudian polinomial dalam input).G $G$$G$$G$
• Untuk input yang posets dengan lebar konstan, kita dapat menggunakan algoritma dinamis mengikuti dekomposisi rantai. Jadi, jika kekerasan bertahan maka harus menggunakan input poset yang lebar sewenang-wenang. Perhatikan bahwa untuk poset lebar, jumlah kemungkinan "status" dalam pendekatan pemrograman dinamis adalah jumlah gangguan poset, yang secara umum bersifat eksponensial dan bukan polinomial, sehingga pendekatan tersebut tidak langsung bekerja.
• Masalah yang sama dapat dipelajari untuk monoid daripada kelompok, tetapi untuk monoid saya sudah tahu bahwa itu sulit, dengan argumen yang cukup berbelit-belit yang melibatkan transisi mono automaton dan mereduksi ke varian dari pertanyaan teori CS sebelumnya . Bukti lengkapnya ada dalam pracetak ini , lampiran D.1.3 dan D.1.4, meskipun terminologinya sangat berbeda. Karenanya, ketika -testing adalah PTIME, ia harus menggunakan invertibilitas elemen grup.$G$
• Jika kami bertanya apakah semua ekstensi linear menyadari (daripada beberapa memang), maka saya tahu masalahnya ada di PTIME (lihat lampiran D.2 dari pracetak yang sama), meskipun saya juga tahu bahwa masalah lain ini adalah coNP- sulit untuk monoid daripada kelompok (D.1.3 dan D.1.4).$e$

Jika -test sulit untuk beberapa , tentu saja, pertanyaan alami adalah apakah beberapa dikotomi memegang, dan yang kriteria akan membedakan penurut dan non-penurut . Sebenarnya pertanyaan ini dapat lebih umum ditanyakan ketika kita menggunakan automata terbatas daripada kelompok. (Secara formal: Perbaiki alfabet hingga , dan otomat hingga deterministik hingga (DFA) A pada Σ , dan pertimbangkan masalah A -test, berikan poset yang dilabeli dengan elemen dari Σ , untuk memeriksa apakah beberapa ekstensi linear membentuk kata yang diterima oleh A. ) Tentu saja saya tidak tahu tentang pertanyaan-pertanyaan sulit ini.G G G $G$$G$$G$$G$$\Sigma$$A$$\Sigma$$A$$\Sigma$$A$

Saya tunjukkan di bawah ini bahwa masalah -test adalah NP-hard untuk beberapa kelompok G sederhana tapi tak terbatas . Kasing terbatas masih terbuka.$G$$G$

bukti

Tentukan fungsi-fungsi berikut: dan g a ( x ) = x + a .$f(x) = -x$$g_a(x) = x + a$

Kemudian ambil menjadi grup yang dihasilkan oleh f dan g a dengan komposisi sebagai operasi.$G$$f$$g_a$

Perhatikan bahwa elemen adalah { f ∘ g a | a ∈ Z } ∪ { g a | a ∈ Z } , jadi ini sebenarnya grup yang cukup sederhana.$G$$\{f \circ g_a | a \in \mathbb{Z} \} \cup \{g_a | a \in \mathbb{Z} \}$

Maka masalah -test adalah NP-hard dengan reduksi dari partisi.$G$

Masalah partisi meminta urutan tertentu bilangan bulat apakah ada partisi dari urutan yang menjadi dua bagian dari jumlah yang sama.$a_1, a_2, ..., a_n$

$P$$n+2$$f$$n$$g_{a_i}$$i = 1,..., n$

$g_p \circ g_q = g_{p+q}$$f \circ g_p \circ f = g_{-p}$$P$$g_{\sum_{i \not\in I}a_i - \sum_{i \in I}a_i}$$I$$g_{a_i}$$f$$g_0$$P$$\sum_{i \not\in I}a_i - \sum_{i \in I}a_i = 0$$\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$

$G$$I$$\sum_{i \not\in I}a_i = \sum_{i \in I}a_i$

$G$$G$

Dengan rekan penulis saya, kami baru saja memposting pracetak yang mempelajari masalah ini secara lebih umum untuk bahasa reguler. Dalam kasus kelompok terbatas, kami mengklaim bahwa masalahnya dapat ditangani (dalam NL) dalam kasus di mana urutan parsial pada elemen terdiri dari gabungan rantai: lihat Teorema 6.2. Kami akan menduga bahwa masalah untuk DAG umum juga di NL, dan ada beberapa harapan untuk memperluas teknik ke pengaturan itu, tetapi kami kehilangan bahan untuk ini, terkait dengan pertanyaan ini - untuk detail, lihat pracetak, Bagian 6, "Batasan" paragraf di akhir, batasan kedua.