Algoritma yang efisien untuk adanya permutasi dengan urutan perbedaan?

Pertanyaan ini dimotivasi oleh postingan ini, Dapatkah Anda mengidentifikasi jumlah dari dua permutasi dalam waktu polinomial? , dan minat saya pada sifat komputasi permutasi.

Sebuah perbedaan urutan dari permutasi nomor dibentuk dengan menemukan perbedaan antara setiap dua angka yang berdekatan dalam permutasi . Dengan kata lain, untuk $a_1, a_2, \ldots a_n$ $\pi$ $1, 2, \ldots n+1$ $\pi$ $a_i= |\pi(i+1)-\pi(i)|$ $1 \le i \le n$

Sebagai contoh, urutan adalah urutan perbedaan permutasi . Sementara, urutan dan bukanlah urutan perbedaan dari permutasi angka . $1, 1, 3$ $2 3 4 1$ $2, 2, 3$ $3, 1, 2$ $1, 2, 3, 4$

Apakah ada algoritma yang efisien untuk menentukan apakah urutan yang diberikan adalah urutan perbedaan untuk beberapa permutasi , atau apakah itu NP-hard? $\pi$

EDIT : Kami mendapatkan masalah yang setara secara komputasi jika kami merumuskan masalah menggunakan permutasi melingkar.

EDIT2 : Lintas diposting di MathOverflow, Seberapa sulit merekonstruksi permutasi dari urutan perbedaannya?

EDIT3 Mendapat hadiah untuk sketsa bukti dan saya akan menerima jawabannya setelah mendapatkan bukti formal lengkap.

EDIT 4 : Bukti kelengkapan -Marzio yang bagus telah dipublikasikan dalam Electronic Journal of Combinatorics . $NP$

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

Mungkin komentar sepele lainnya (tetapi lebih banyak suara?) Adalah bahwa jika

adalah permutasi dari

(semua nilai berbeda) maka masalahnya adalah untuk memverifikasi bahwa urutannya adalah pelabelan anggun dari garis

node yang dipecahkan dalam waktu polinomial.

a_{i}

$a_i$

[1.. n]

$[1..n]$

n + 1

$n+1$

Marzio De Biasi

@MarzioDeBiasi Sepertinya Anda berbagi hasrat saya untuk masalah permutasi. Saya harap saya mendapatkan masalah permutasi yang paling menarik secara komputasi :)

Mohammad Al-Turkistany 5'13

:-) ... Saya lebih suka mengatakan bahwa komentar saya datang langsung dari jam yang saya habiskan dengan sia-sia pada masalah pelabelan pohon anggun ... namun saya punya ide kabur dari kemungkinan pengurangan NP-lengkap untuk masalah Anda; jika saya berhasil memformalkannya, saya akan mengirim jawaban.

Marzio De Biasi

@MarzioDeBiasi Saya menemukan komentar menarik ini oleh Shor yang menyatakan bahwa masalah Anda, Penjadwalan pekerjaan dengan masalah bottleneck , setara dengan kasus khusus masalah saya. Berikut adalah komentar Shor: jika

, masalahnya setara dengan menemukan permutasi

sehingga

K = 2 N

$K=2N$

1...2 N

$1...2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a−1}−i_{2a}=A_i$ . Ini memberikan bukti lain dari

-completeness dari masalah saya.

N P

$NP$

Mohammad Al-Turkistany

Jawaban:

Ini adalah sketsa pengurangan yang mungkin untuk membuktikan bahwa NP-hard:

$a_i$ $...11111...$

$2$ $1112112111$

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

Lubang-lubang harus diisi dengan sisa permutasi.

3) menggunakan 1SEQ cukup besar, diikuti oleh 1SEQ dengan beberapa lubang, diikuti oleh 1SEQ besar Anda dapat membangun garis paksa ;

4) menyusun banyak garis paksa Anda dapat membangun grafik kotak permutasi di mana node sesuai dengan angka yang hilang dalam permutasi paksa yang mendasarinya.

Misalnya urutan 1111111112111111111112111111111, memaksa grafik kotak permutasi 5x7 berikut:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7

$w \times w$ $a,b$ $|a-b|=kw$

$G$

$G$ $G$

7) Anda dapat mengisi semua lubang (yaitu menyelesaikan permutasi) jika dan hanya jika grafik kotak asli memiliki siklus Hamiltonian

EDIT: 27 Juli 2013

Saya mencoba untuk secara resmi membuktikan kelengkapan NP masalah: Saya memperkenalkan masalah baru (masalah Crazy Frog ) yaitu NPC. Permutasi Rekonstruksi dari masalah Perbedaan setara dengan "1-D Crazy Frog masalah tanpa sel diblokir" (yang juga NPC).

Untuk detail pengurangan lihat pertanyaan saya / jawaban pada cstheory "Dua varian jalur Hamiltonian" atau unduh konsep bukti "Ketika katak bertemu permutasi" :)) (saya masih memeriksa / menyelesaikannya)

Marzio De Biasi
sumber

Bagus, saya yakin ini akan mengarah pada solusi, pemilihan gadget pasti dapat direalisasikan.

domotorp

@domotorp: Saya mempostingnya (saya akan memposting detail bagian pilih / sinkronisasi di hari-hari berikutnya); mungkin berisi kesalahan yang tidak saya lihat, namun saya bertaruh $ 1 bahwa seluruh pengurangan bisa sangat disederhanakan :-)

Marzio De Biasi

@MarzioDeBiasi Visualisasi yang bagus. Tampaknya Anda berada di jalur yang benar. Bisakah Anda memposting jawaban Anda di MathOverflow karena ada minat yang besar terhadap masalah ini?

Mohammad Al-Turkistany

@MarzioDeBiasi Bisakah Anda memposting jawaban akhir Anda (formal) sebelum hadiahnya berakhir?

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Saya baru saja kembali dari perjalanan, saya akan mencoba memformalkan (dan memeriksa dengan CSP) gadget di hari-hari berikutnya.

Marzio De Biasi