Apakah masalah “subset produk” NP-selesai?

Masalah subset-jumlah adalah masalah klasik NP-complete:

Diberikan daftar angka dan target , adakah subset angka dari yang menjumlahkan ke ? $L$ $k$ $L$ $k$

Seorang siswa bertanya kepada saya apakah varian masalah yang disebut masalah "subset produk" ini adalah NP-complete:

Diberikan daftar angka dan target , adakah subset angka dari yang produknya ? $L$ $k$ $L$ $k$

Saya melakukan pencarian dan tidak dapat menemukan sumber daya yang membicarakan masalah ini, meskipun mungkin saya merindukan mereka.

Apakah masalah subset produk NP-selesai?

complexity-theory np-complete reductions templatetypedef
sumber

Jawaban yang menarik, tapi saya bertanya-tanya: Tidak bisakah kita mengurangi menjadi Subset Jumlah hanya dengan mengambil log k dan semua angka? (Mungkin saya harus mengajukan pertanyaan terpisah?)

j_random_hacker

@ j_random_hacker, ya, jika Anda tidak dapat menemukan jawaban setelah mencari di situs ini dan online, saya sarankan Anda memposting pertanyaan terpisah. Ini adalah pertanyaan yang bagus dengan jawaban yang bagus (petunjuk: mengambil log memberi Anda sesuatu yang bukan bilangan bulat; di arah lain, pikirkan tentang apa yang dilakukan eksponensial terhadap ukuran angka), tetapi itu sedikit singgung dan akan lebih baik dalam pertanyaannya sendiri.

@ WD: Terima kasih, ketika saya punya waktu saya akan melakukan seperti yang Anda sarankan!

j_random_hacker

Jawaban:

Sebuah komentar menyebutkan pengurangan dari X3C ke SUBSET PRODUCT yang dikaitkan dengan Yao. Mengingat target pengurangan itu, tidak sulit untuk menebak apa kemungkinan penurunan itu.

Definisi:

SAMPUL SAMBUTAN DENGAN 3-SET (X3C)

Diberi himpunan terbatas dengankelipatan dari 3, dan kumpulan dari himpunan bagian 3-elemen dari , apakah berisi penutup tepat untuk , di mana dan setiap elemen dalam terjadi tepat sekali dalam ? $X$ $|X|$ $C$ $X$ $C$ $C'$ $X$ $C' \subseteq C$ $X$ $C'$

PRODUK SUBSET

Diberikan daftar angka dan target , adakah subset angka dari yang produknya ? $L$ $k$ $L$ $k$

Untuk mengurangi instance X3C ke instance PRODET SUBSET:

Buat pemetaan dua arah antara anggota dan yang pertamabilangan prima. Ganti anggota dan himpunan bagian dengan bilangan prima yang dipetakan. $X$ $|X|$ $X$ $C$
Untuk setiap subset dalam , gandakan anggotanya bersama-sama; daftar produk yang dihasilkan adalah untuk instance PRODUK SUBSET. Karena bilangan prima digunakan untuk pemetaan pada langkah 1, produk dijamin akan setara jika himpunan bagiannya setara dengan teorema faktorisasi unik . $C$ $L$
Lipat gandakan anggota bersama-sama; produk yang dihasilkan adalah nilai untuk instance PRODUK SUBSET. $X$ $k$

Faktor prima dari persis anggota . Faktor prima dari angka-angka dalam berhubungan persis dengan anggota himpunanOleh karena itu setiap solusi untuk contoh SUBSET PRODUK baru dapat diubah menjadi solusi X3C dengan memetakan anggota larutan kembali ke subset di . $k$ $X$ $L$ $C$ $L$ $C$

Masing-masing dari 3 langkah transformasi melibatkan operasi yang jumlahnya banyak dengan ukuran inputatau ukuran anggota dari . Yang pertamabilangan prima dapat dihasilkan dalam waktu O ( ) menggunakan saringan Eratosthenes dan dijamin sesuai dengan ruang oleh teorema bilangan prima . $|X|$ $X$ $|X|$ $|X|$ $O(|X|^2 \ln |X|)$

Kyle Jones
sumber

+1, tetapi untuk pengurangan yang harus dilalui saya pikir kita mengharuskan yang pertama | X | bilangan prima dapat direpresentasikan dalam sejumlah bit yang jumlahnya banyak dalam | X | - Apakah saya benar tentang ini, dan jika demikian, apakah kita memiliki jaminan itu?

j_random_hacker

Poin luar biasa. Saya telah menambahkan paragraf ke alamat itu.

Kyle Jones

Terima kasih, teorema itu membuatnya! Bukan untuk melakukan nitpick, tetapi menurut halaman yang Anda tautkan, bilangan prima kth adalah sekitar k log k, dan mengingat bahwa Saringan Eratosthenes tampaknya menghitung semua bilangan prima hingga n dalam waktu O (n log log n) , menggantikan n = k log k muncul untuk memberikan waktu O (k * log (k) * log (log (k log k))), daripada O (k) (O (| X |)) Anda, untuk menghitung k pertama banggakan itu.

j_random_hacker

Kyle Jones, bukankah sangat penting bahwa langkah 3 akan membuat sejumlah

ukuran eksponensial? Apakah pengurangan ini benar-benar waktu polinomial?

k

$k$

user1742364

@ user1742364 Tidak, karena komputasi

tidak memerlukan sejumlah operasi eksponensial atau memerlukan penyimpanan sejumlah bit eksponensial. Komputasi

membutuhkan

perkalian dan perkalian paling buruk adalah operasi

. Sementara

akan secara eksponensial lebih besar dari prime

terbesar di

, jumlah bit yang dibutuhkan untuk menyimpan

adalah

k

$k$

k

$k$

| X |

$|X|$

O (n^{2})

$O(n^2)$

k

$k$

P

$P$

X

$X$

k

$k$

O (\log P)

$O(\log P)$

Kyle Jones

Menurut [ 1 ]: Ya itu

Saya juga mengutip referensi yang sama: Komentar: Ada perbedaan teknis yang halus antara ini dan Masalah 42: kasus sebelumnya memiliki algoritma pseudo-efisien yang diperoleh dengan memungkinkan angka untuk diwakili di unary; kecuali semua masalah NP-selesai dapat diselesaikan dengan algoritma cepat, namun, Masalah Produk Subset, tidak dapat diselesaikan dengan metode `efisien 'menggunakan bahkan representasi input yang tidak masuk akal ini.

lihat [2] untuk reduksi. [2]: Fellows, Michael, dan Neal Koblitz. "Kompleksitas parameter tetap dan kriptografi." Aljabar Terapan, Aljabar Aljabar, dan Kode Koreksi Kesalahan (1993): 121-131.

Dipotong
sumber

Pengurangan atau kutipan aktual dalam artikel jurnal akan menyenangkan, jika mungkin.

templatetypedef

@templatetypedef Di Garey dan Johnson, reduksi ke sampul tepat sebanyak 3 set. Karena komunikasi pribadi dengan Yao.

AJed

Pengurangan dalam kertas kriptografi adalah untuk masalah yang berbeda, di mana produk target diganti oleh kongruensi dengan nomor target modulo modulus yang diberikan dalam contoh. (Meskipun jika saya memahami buktinya dengan benar, mereka hanya mendapatkan kekerasan yang lemah karena modulus besarnya eksponensial.)

Jeffrey Bosboom