mengenali perbedaan dua permutasi

Shor menyatakan, dalam komentarnya pada jawaban moose anonim untuk pertanyaan ini Bisakah Anda mengidentifikasi jumlah dua permutasi dalam waktu polinomial? , bahwa -complete untuk mengidentifikasi perbedaan dua permutasi. Sayangnya, saya tidak melihat pengurangan langsung dari masalah jumlah permutasi dan berguna untuk memiliki pengurangan - untuk masalah perbedaan permutasi. $NP$ $NP$

Perbedaan Permutasi:

INSTAN: Array dari bilangan bulat positif. $A[1...n]$

PERTANYAAN: Apakah ada dua permutasi dan dari bilangan bulat positif sedemikian rupa sehingga untuk ? $\pi$ $\sigma$ $1,2, ... , n$ $|\pi(i) - \sigma(i)| = A[i]$ $1 \le i \le n$

Apa pengurangan untuk membuktikan - mengenali perbedaan dua permutasi? $NP$

EDIT 2014/10/09 : komentar Shor memberikan pengurangan yang membuktikan -completeness ketika unsur-unsur dari urutan yang ditandatangani perbedaan. Namun, saya tidak melihat pengurangan yang mudah untuk masalah saya di mana semua elemen adalah nilai absolut dari perbedaan. $NP$ $A$ $A$

UPDATE: Masalah Perbedaan Permutasi tampaknya lengkap bahkan jika salah satu dari dua permutasi selalu permutasi identitas. Bukti kekerasan dari kasus khusus ini sangat disambut baik. Jadi, saya tertarik pada versi terbatas ini: $NP$ $NP$

Perbedaan Permutasi Terbatas: INSTANSI: Array dari bilangan bulat positif. $A[1...n]$

~~PERTANYAAN: Apakah ada permutasi dari bilangan bulat positif sedemikian rupa sehingga untuk ? $\pi$ $1,2, ... , n$ $|\pi(i) - i| = A[i]$ $1 \le i \le n$~~

Pembaruan 2 : Masalah yang dibatasi ditentukan secara efisien seperti yang ditunjukkan oleh jawaban mjqxxxx. Kompleksitas komputasi dari masalah aslinya tidak terbukti.

EDIT 9/6/16 : Saya tertarik untuk menentukan apakah penyederhanaan Perbedaan Permutasi ini adalah NP-complete:

Perbedaan Permutasi Terbatas:

Instance : Sebuah multiset bilangan bulat positif. $A$

PERTANYAAN : Apakah ada permutasi dari bilangan bulat positif sehingga ? $\pi$ $1,2, ... , n$ $A= \{|\pi(i) - i| :1 \le i \le n\}$

cc.complexity-theory co.combinatorics np-hardness permutations Mohammad Al-Turkistany
sumber

Mengapa tidak bertanya langsung kepada Peter? @ Peter

caozhu

Apakah yang Anda maksud dengan Email? Saya akan melakukan itu.

Mohammad Al-Turkistany

Saya mungkin kehilangan sesuatu tetapi tidak bisakah masalah ini direpresentasikan sebagai 2-SAT dan karenanya diselesaikan dalam polytime? Kita dapat mengasumsikan WLOG bahwa salah satu permutasi adalah identitas (saya mengasumsikan di sini bahwa A [i] dihitung secara siklis; haruskah itu sangat berarti?), Dan kemudian kita dapat mewakili yang kedua dengan matriks

. Menjadi matriks permutasi adalah konjungsi dari klausa dua variabel yang menyatakan bahwa tidak ada dua yang terletak di baris atau di kolom; dan kemudian mengatakan bahwa perbedaannya ada di lokasi pi (i) dari i adalah A [i] adalah OR dari dua tempat yang memungkinkan.

x [i, j]

$x[i,j]$

Noam

@Noam Terima kasih atas komentar Anda. Ide yang menarik. Saya tidak memikirkannya. Namun, tidak jelas bagi saya apakah akan mengarah ke algoritma waktu polinomial terutama bahwa kita hanya diberi nilai absolut dari perbedaan.

Mohammad Al-Turkistany

Ya, tampaknya perbedaan antara menghitung kesenjangan secara siklikal atau nilai absolut dapat menjadi masalah.

Noam

Jawaban:

Masalahnya dibatasi, di mana salah satu permutasi adalah identitas, tentu di . Bangun grafik bipartit di mana setiap simpul terhubung ke elemen (s) sedemikian rupa sehingga . Kemudian permutasi yang diinginkan $\mathsf{P}$ $i \in V_1=\{1,2,\ldots,n\}$ $j \in V_2=\{1,2,\ldots,n\}$ $|i-j|=A[i]$ $\sigma$ ada jika dan hanya jika grafik memiliki pencocokan sempurna (yaitu pencocokan dengan edge), yang dapat ditentukan dalam waktu polinomial. $n$

mjqxxxx
sumber

Saya mungkin kehilangan sesuatu, tetapi kecocokan yang sempurna tidak akan berhasil. Anda harus membuktikan adanya pencocokan sempurna terbatas. Pertimbangkan integer

yang terjadi dua kali dalam masukan berbagai

. Pencocokan sempurna yang sesuai dengan permutasi harus memiliki dua sisi dengan perbedaan absolut

. Algoritma Anda TIDAK membuktikan keberadaan pencocokan terbatas tersebut. Inilah yang membuat masalah sulit dan mungkin NP-lengkap.

k

$k$

A

$A$

k

$k$

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Saya pikir jika

maka

ditautkan ke node

A [i] = A [j] = k

$A[i] = A[j] = k$

u_{i}, u_{j} \in V_{1}

$u_i, u_j \in V_1$

v_{i + A [i]}, v_{i - A [i]}, v_{j + A [j]}, v_{j - A [j]} \in V_{2}

$v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ dengan perbedaan absolut

. Pencocokan sempurna akan mencakup setidaknya satu ujung dari

dan salah satu ujung dari

. Saya sampai pada kesimpulan yang sama beberapa kali yang lalu sambil memikirkan masalah aslinya, tetapi mengikuti cara lain: Saya melihat bahwa mudah untuk merumuskan masalah terbatas sebagai rumus 2-SAT (jika Anda mau, saya dapat menambahkan jawaban dengan itu , tapi ide mjqxxxx lebih baik).

k

$k$

u_{i}

$u_i$

u_{j}

$u_j$

Marzio De Biasi

@MarzioDeBiasi Mengapa pendekatan ini (dan milik Anda) tidak berfungsi untuk masalah asli (tidak dibatasi)?

Mohammad Al-Turkistany

@ mjqxxx Saya melihat bahwa pendekatan Anda menyelesaikan kasus terbatas. Mengapa tidak bisa diperluas untuk secara efisien menyelesaikan masalah aslinya?

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: karena dalam masalah awal elemen permutasi pertama (

dalam versi terbatas) tidak diperbaiki, dan menggunakan pendekatan yang sama Anda berakhir dengan grafik tripartit (dan dalam pendekatan 2-SAT saya dengan a

klausa ... yang bukan klausa 2-CNF).

i

$i$

δ_{i} (n) \to (π_{i} (n + A [i]) \lor π_{i} (n - A [i]))

$\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$

Marzio De Biasi

Berikut adalah variasi yang agak menarik di mana masalahnya mudah: alih-alih set ground dari , izinkan setiap subset dari . Tujuannya masih untuk menemukan permutasi sehingga mana $\{1,2,3,\ldots,n\}$ $\{1,2,4,8,\ldots\}$ $\pi$ $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$ $\Omega$ adalah ground set. Keuntungan utama di sini adalah bahwa himpunan ground baru memaksa setiap elemen menjadi untuk beberapa , dan jika , maka dan ditentukan oleh ini perbedaan. Oleh karena itu untuk setiap perbedaan dalam , kita dapat menyimpulkan bahwa $A$ $2^{k_1}-2^{k_2}$ $k_1,k_2$ $k_1\ne k_2$ $k_1$ $k_2$ $|2^{k_1} - 2^{k_2}|$ $A$ atau (atau keduanya). $\pi(2^{k_1}) = 2^{k_2}$ $\pi(2^{k_2}) = 2^{k_1}$

Memecahkan variasi yang disederhanakan ini secara efisien lebih atau kurang rutin. Mulailah dengan membuat multigraf bipartit tidak berarah mana dan adalah salinan berbeda dari perangkat ground, dan tambahkan tepi dan kapan saja muncul di $G = (L \sqcup R, E)$ $L$ $R$ $(2^{k_1},2^{k_2})$ $(2^{k_2},2^{k_1})$ $|2^{k_1} - 2^{k_2}|$ dengan . Saya mengklaim bahwa yang berikut ini setara: $A$ $k_1 \ne k_2$

Ada permutasi dengan perbedaan $\pi$ $A$
Setiap simpul dalam memiliki derajat 0 atau 2 $G$

Saya tidak akan benar-benar membuktikan ini karena waktu, tetapi tidak terlalu buruk untuk mengerjakannya sendiri. Itu sangat mudah. Itu $1 \implies 2$ sedikit lebih sulit, tetapi tidak terlalu buruk ketika Anda beralasan dengan automorfisme yang mengirim setiap simpul dalam ke salinannya dalam (dan sebaliknya). Bukti yang ada dalam pikiran saya mengarahkan tepi dalam sehingga semua tepi dalam siklus pergi `` dengan cara yang sama di sekitar siklus '' (setiap simpul nonisolasi memiliki in-degree = out-degree = 1), dan sehingga sebelumnya automorfisme tetap merupakan automorfisme versi terarah. kemudian dipilih sesuai dengan tepi yang pergi dari ke . $2 \implies 1$ $G$ $L$ $R$ $G$ $G$ $\pi$ $L$ $R$

Anda dapat menggunakan algoritme di atas sebagai pertanyaan pencocokan sempurna, dan saya membayangkan ada pengurangan lain pada 2-SAT. Saya tidak melihat bagaimana memperluas pendekatan ini ke masalah aslinya.

Andrew Morgan
sumber