Deteksi hubungan integer untuk Jumlah Subset atau NPP?

Apakah ada cara untuk menyandikan turunan dari Jumlah Subset atau Masalah Partisi Angka sehingga solusi (kecil) untuk hubungan bilangan bulat menghasilkan jawaban? Jika tidak pasti, maka dalam arti probabilistik?

Saya tahu bahwa LLL (dan mungkin PSLQ) telah digunakan dengan keberhasilan sedang dalam memecahkan masalah Subset Sum di wilayah 'kepadatan rendah', di mana kisaran angka yang dipilih lebih besar dari , tetapi metode ini tidak berskala baik untuk contoh ukuran yang lebih besar dan gagal di wilayah 'high-density', ketika kisaran angka yang dipilih adalah jauh lebih kecil dari . Di sini low-density dan high-density mengacu pada sejumlah solusi. Wilayah kepadatan rendah mengacu pada sedikit atau tidak ada solusi yang ada sedangkan kepadatan tinggi mengacu pada daerah dengan banyak solusi. $2^N$ $2^N$

Di wilayah kepadatan tinggi, LLL menemukan hubungan integer (kecil) di antara instance yang diberikan, tetapi saat ukuran instance meningkat, probabilitas relasi yang ditemukan menjadi solusi Subset Sum atau Number Partition Problem menjadi semakin kecil.

Deteksi hubungan integer bersifat polinomial dalam batas eksponensial optimal sedangkan Subset Sum dan NPP jelas NP-Lengkap, jadi secara umum ini mungkin tidak mungkin, tetapi jika instance diambil secara seragam secara acak, dapatkah ini membuatnya lebih sederhana?

Atau haruskah saya bahkan tidak mengajukan pertanyaan ini dan malah bertanya apakah ada cara untuk mengurangi batas eksponensial dari jawaban optimal sebagai pengganti peningkatan eksponensial dalam perhitungan?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum pengguna834
sumber

Saya tidak mendapatkan jawaban, jadi saya mengirim pesan silang ke mathoverflow: mathoverflow.net/questions/38063/…

user834

Ini pertanyaan yang sangat menarik, saya juga menunggu jawaban. Anda pada dasarnya meminta pengurangan waktu polinomial (mungkin acak) dari jumlah Subset atau NPP ke hubungan integer. Bagaimana dengan ini, jika

adalah target masalah jumlah himpunan bagian Anda, dan

adalah himpunan bilangan bulat positif, dengan

solusi yang memuaskan

. Ini adalah persis kombinasi linear dengan koefisien nyata sama dengan 1. Jika untuk setiap

Anda memiliki

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

selalu ada solusi, dan pemetaan ke hubungan integer juga akan memberi Anda solusi.

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

Marcos Villagra

@Marcos Villagra: komentar Anda agak sulit untuk diurai ... orang dapat menanamkan masalah sebagai masalah jumlah subset / partisi nomor menjadi kisi (lihat di sini untuk ulasan), pertanyaannya adalah menemukan cara untuk membatasi koefisien ke set yang diinginkan (0,1 atau -1,1, katakanlah). LLL akan menemukan hubungan integer, bahkan yang kecil, tetapi hanya satu 2 atau 3 sebagai koefisien akan membatalkannya sebagai bagian jumlah / nomor jawaban subset.

user834

Biarkan m menjadi logaritma angka terbesar. Jika maka dapat dipecahkan dalam waktu polinomial menggunakan pemrograman dinamis. Secara umum, setiap algoritma yang diketahui membutuhkan setidaknya waktu. Tidak ada algoritma waktu polinomial yang dikenal ketika dan $m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

Namun, Flaxman dan Przydatek menyediakan algoritma yang memecahkan Masalah Jumlah Subset Sedang-Densitas dalam Waktu Polinomial yang Diharapkan.

Periksa referensi ini:

Flaxman dan Przydatek, Memecahkan Masalah Jumlah Subset Sedang-Densitas dalam Waktu Polinomial yang Diharapkan

Mohammad Al-Turkistany
sumber

Hasil ini hanya untuk memilih angka-angka dalam instance Subset Sum secara signifikan lebih rendah daripada yang saya inginkan. Mereka memilih kisaran angka pada urutan log (n) ^ 2 sedangkan saya menarik dalam kisaran angka pada urutan 2 ^ n. Ada algoritma yang terkenal untuk menyelesaikan Subset Sum ketika kisaran angka dibatasi sangat rendah dan sepertinya mereka baru saja memperluas kisaran ini sedikit, yang hebat, hanya saja bukan yang saya cari. Terima kasih.

user834

Deteksi hubungan integer untuk Jumlah Subset atau NPP?

Jawaban: