Ada dua pertanyaan yang diajukan baru-baru ini di cs.se yang terkait atau memiliki kasus khusus yang setara dengan pertanyaan berikut:
Misalkan Anda memiliki urutan dari n angka sehingga Σ n i = 1 a i = n ( n + 1 ) . Uraikan menjadi jumlah dari dua permutasi, π dan σ , dari 1 ... n , sehingga a i = π i + σ i.
Ada beberapa kondisi yang diperlukan: jika diurutkan sehingga suatu 1 ≤ a 2 ≤ ... ≤ a n, maka kita harus punya
Namun, kondisi ini tidak memadai. Dari jawaban untuk pertanyaan math.se ini saya bertanya, urutan 5,5,5,9,9,9 tidak dapat didekomposisi sebagai jumlah dari dua permutasi (satu dapat melihat ini dengan menggunakan fakta bahwa kedua 1 atau 5 hanya bisa dipasangkan dengan 4).
Jadi pertanyaan saya adalah: apa kompleksitas masalah ini?
Jawaban:
Tidak, Anda tidak dapat mengidentifikasi jumlah dua permutasi dalam waktu polinomial kecuali P = NP. Masalah Anda adalah NP-complete karena versi keputusan dari masalah Anda sama dengan NP-complete problem -Pencocokan numerik dengan jumlah target:2
Input: Urutan bilangan bulat positif, Σ n i = 1 a i = n ( n + 1 ) , 1 ≤ a i ≤ 2 n untuk 1 ≤ i ≤ na1,a2,…an ∑ni=1ai=n(n+1) 1≤ai≤2n 1≤i≤n
Pertanyaan: Apakah ada dua permutasi dan ψ 2 sedemikian rupa sehingga ψ 1 ( i ) + ψ 2 ( i ) = a i untuk 1 ≤ i ≤ n ?ψ1 ψ2 ψ1(i)+ψ2(i)=ai 1≤i≤n
Dalam referensi, varian yang sangat terbatas dari NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) terbukti sangat lengkap dengan NP.
Ada pengurangan yang mudah dari RN3DM ke -Numerical Matching dengan masalah jumlah target: Diberikan turunan dari RN3DM. Kami membangun sesuai misalnya dengan membuat sebuah i = e - u i untuk 1 ≤ i ≤ n2 ai=e−ui 1≤i≤n
W. Yu, H. Hoogeveen, dan JK Lenstra. Meminimalkan makespan di toko aliran dua mesin dengan penundaan dan operasi unit-waktu adalah NP-hard . Jurnal Penjadwalan, 7: 333-348, 2004
Sunting 1 Oktober : Masalah Anda disebut SUMBER PERMUTASI. Ini terdaftar sejak tahun 1998 dalam MASALAH TERBUKA DALAM OPTIMASI KOMBINATORIAL oleh Steve Hedetniemi.
sumber
Di sisi lain, Marshall Hall menunjukkan bahwa adalah mungkin untuk mengidentifikasi perbedaan dua permutasi dengan mudah.
sumber