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 ?
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?
Jawaban:
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:
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 ...
sumber