Kemungkinan menghasilkan permutasi yang diinginkan dengan swap acak

Saya tertarik dengan masalah berikut. Kami diberikan sebagai masukan "target permutasi" , serta daftar memerintahkan indeks . Kemudian, dimulai dengan daftar (yaitu, permutasi identitas), pada setiap langkah waktu kita menukar elemen dalam $\sigma\in S_n$ $i_1,\ldots,i_m\in [n-1]$ $L=(1,2,\ldots,n)$ $t\in [m]$ $i_t^{th}$ $L$ dengan elemen, dengan probabilitas independen . Misalkan adalah probabilitas bahwa diproduksi sebagai output. $(i_t+1)^{st}$ $1/2$ $p$ $\sigma$

Saya ingin tahu (ada) yang berikut ini:

Adalah memutuskan apakah merupakan -Lengkap masalah? $p>0$ $NP$
Apakah menghitung tepat -lengkap? $p$ $\#P$
Apa yang bisa kita katakan tentang perkiraan ke dalam konstanta multiplikatif? Apakah ada PTAS untuk ini? $p$

Varian di mana swap tidak perlu elemen yang berdekatan juga menarik.

Perhatikan bahwa tidak sulit untuk mengurangi masalah ini menjadi jalur edge-disjoint (atau untuk multicommodity flow yang bernilai integer); apa yang saya tidak tahu adalah pengurangan ke arah lain.

Pembaruan: Oke, memeriksa Garey & Johnson, masalah mereka [MS6] ("Generasi Permutasi") adalah sebagai berikut. Diberikan sebagai input permutasi target , bersama dengan himpunan bagian , memutuskan apakah dapat diekspresikan sebagai produk , di mana setiap bertindak secara sepele pada semua indeks yang tidak dalam . Garey, Johnson, Miller, dan Papadimitriou (di belakang paywall, sayangnya) membuktikan bahwa masalah ini adalah $\sigma\in S_n$ $S_1,\ldots,S_m\in [n]$ $\sigma$ $\tau_1 \cdots \tau_m$ $\tau_i$ $S_i$ Keras. $NP$

$p>0$ $NP$ $S_1,S_2,\ldots$ $S_i$ $S_i$ $\sigma$ $\tau_1 \cdots \tau_m$

$\#P$ $P=NP$

np-hardness counting-complexity permutations sorting-network disjoint-paths Scott Aaronson
sumber

Tidak yakin saya mengerti pertanyaannya. Di mana probabilitas datang? Apakah Anda menukar dengan probabilitas 1/2 dan tidak dengan probabilitas 1/2?

arnab

| S_{i} | = 2

$|S_i|=2$

Jawaban:

Saya pikir apakah p> 0 dapat diputuskan dalam waktu polinomial.

Masalah yang dimaksud dapat dengan mudah dilemparkan sebagai masalah path-disjoint paths, di mana grafik yang mendasari adalah grafik planar yang terdiri dari m +1 lapisan yang masing-masing berisi n simpul, ditambah m derajat-4 simpul untuk mewakili kemungkinan pertukaran yang berdekatan. Perhatikan bahwa planaritas grafik ini mengikuti dari fakta bahwa kami hanya mengizinkan swap yang berdekatan.

Jika saya tidak salah, ini termasuk dalam kasus khusus dari masalah edge-disjoint paths yang diselesaikan oleh Okamura dan Seymour [OS81]. Selain itu, Wagner dan Weihe [WW95] memberikan algoritma linear-waktu untuk kasus ini.

Lihat juga catatan kuliah Goemans [Goe12], yang memberikan penjelasan bagus tentang teorema Okamura-Seymour dan algoritma Wagner-Weihe.

Referensi

[Goe12] Michel X. Goemans. Catatan Kuliah, 18.438 Optimalisasi Combinatorial Lanjutan, Kuliah 23 . Massachusetts Institute of Technology, Spring 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura dan Paul D. Seymour. Multikomoditas mengalir dalam grafik planar. Jurnal Teori Kombinatorial, Seri B , 31 (1): 75–81, Agustus 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner dan Karsten Weihe. Algoritma linear-waktu untuk jalur edge-disjoint dalam grafik planar. Combinatorica , 15 (1): 135–150, Maret 1995. http://dx.doi.org/10.1007/BF01294465

Tsuyoshi Ito
sumber