Bisakah kita memutuskan apakah seorang permanen memiliki istilah yang unik?

16

Misalkan kita diberi n oleh n matriks, M, dengan entri bilangan bulat. Bisakah kita memutuskan di P apakah ada permutasi sehingga untuk semua permutasi kita memiliki ?σπσΠMiσ(i)ΠMiπ(i)

Catatan. Seseorang tentu saja dapat mengganti produk dengan jumlah, masalahnya tetap sama.

Jika matriks hanya dapat memiliki 0/1 entri, maka kita mendapatkan masalah Bipartite-UPM yang bahkan ada di NC.

Sunting: Memutuskan apakah istilah terkecil itu unik adalah NP-hard jika kami mengizinkan pengurangan acak. Sebenarnya, saya awalnya ingin mengajukan pertanyaan ini, karena akan membantu menyelesaikan yang ini . Sekarang ternyata ini NP-complete, jadi izinkan saya membuat sketsa pengurangan untuk masalah kita. Bayangkan bahwa inputnya adalah matriks zero-one (dapat kita duga) dan ganti entri nol dengan bilangan real acak antara 2 dan 2 + 1 / n. Sekarang dalam matriks baru ini dengan probabilitas tinggi istilah terkecil adalah unik jika dan hanya jika matriks asli diizinkan untuk bentuk segitiga atas.

Edit: Pertanyaan serupa:

Dalam grafik tepi-tertimbang, apakah ada siklus Hamiltonian dengan bobot yang unik?

Jika kita memiliki CNF dengan bobot yang ditetapkan untuk setiap variabel / pemenuhan yang memuaskan, adakah tugas unik yang memuaskan?

Ini tentu saja setidaknya NP-hard. Apakah masalah ini setara dengan yang asli atau lebih sulit?

domotorp
sumber
Apakah kita tahu jika masalah ini bahkan ada di NP? Saya mengalami kesulitan membuat sertifikat.
mhum
@humhum: Batas atas yang paling jelas adalah , seperti yang ditunjukkan Scott Aaronson dalam jawabannya. Saya tidak berpikir ada batas atas yang lebih baik yang diketahui. Σ2P
Joshua Grochow

Jawaban:

13

Masalah bagus! Tidak sulit untuk memberikan pengurangan yang menunjukkan bahwa, jika seseorang dapat memecahkan masalah Anda, maka seseorang juga dapat memecahkan masalah berikut, sebut saja SUMBER SUMBER ISOLASI:

Bilangan bulat diberi 1 , ..., a n , ada subset S dari sebuah i 's yang jumlahnya tidak dimiliki oleh setiap bagian lain?

Pengurangan bekerja dengan terlebih dahulu mengurangi SUMBER SUBSET ISOLASI menjadi PENCOCOKAN SEMPURNA YANG DIISOLASI, di mana diberi grafik bipartit G tertimbang, kami ingin menemukan pencocokan sempurna yang bobotnya tidak dibagi dengan pencocokan sempurna lainnya. Pengurangan ini sederhana: untuk setiap i, buat subgraf lengkap 2x2 G i di G, sedemikian sehingga dari dua kemungkinan kecocokan yang kami pilih untuk G i mengkodekan pilihan kami apakah i ada di set S.

Selanjutnya, kurangi PENCOCOKAN SEMPURNA YANG TERISOLASI untuk masalah Anda sebagai berikut:

  1. Untuk semua i, j, jika tepi (i, j) ada dan memiliki bobot w ij , maka atur M ij : = exp (w ij ). (Ini mengubah jumlah menjadi produk.)
  2. Untuk semua i, j, jika tepi (i, j) tidak ada, maka atur M ij : = 0.
  3. Pad M untuk memastikan bahwa ada dua atau lebih permutasi π sedemikian rupa sehingga Π M i, π (i) = 0. (Ini mengesampingkan solusi palsu yang tidak sesuai dengan pencocokan sempurna di G.)

Sekarang, SUMU ISOLASI SUDUT tentu terasa seperti setidaknya NP-keras, dan mungkin bahkan lebih sulit dari itu (batas atas yang jelas hanya Σ 2 P)! Lebih jauh lagi, mungkin seseorang dapat membuktikan bahwa SUM SUBSET ISOLASI adalah NP-hard menggunakan reduksi gaya acak Valiant-Vazirani. Ini, bagaimanapun, adalah tantangan yang saya serahkan kepada orang lain ...

Scott Aaronson
sumber
Ya, ini setara. Faktanya, jika Anda memeriksa masalah terbuka yang saya coba selesaikan, Anda dapat melihat bahwa saya berasal dari masalah PENCOCOKAN SEMPURNA YANG DIisolasi. Mungkin orang bisa menemukan pengurangan ke / dari masalah Koin Frobenius.
domotorp
4
Duhhh ... Andy Drucker dengan senang hati menunjukkan bahwa masalah SUM SUBSET ISOLASI saya sepele untuk dipecahkan! Jika beberapa a_i adalah 0, maka tidak ada jumlah unik; jika tidak, ambil himpunan semua a_i yang berbagi tanda yang sama (baik positif atau negatif) Jadi, kita harus fokus pada PENCOCOKAN SEMPURNA YANG DIisolasi.
Scott Aaronson