Subset sum vs Subset product (kekerasan NP kuat vs lemah)

Saya berharap bahwa seseorang mungkin dapat menjelaskan kepada saya mengapa masalah subset produk sangat NP-hard sedangkan masalah subset sum lemah NP-hard.

Subset Sum: Mengingat dan , tidak terdapat subset sehingga . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\sum_{i\in X'}x_i = T$

Subset Produk: Mengingat dan , tidak terdapat subset sehingga . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\prod_{i\in X'}x_i = T$

Saya selalu berpikir dua masalah itu setara - sebuah instance dari SS dapat ditransformasikan ke sebuah instance dari SP melalui eksponensial dan sebuah instance dari SP ke SS melalui logaritma. Ini membuat saya menyimpulkan bahwa mereka berdua termasuk dalam kelas NP-hard yang sama - yaitu, mereka keduanya NP-hard lemah.

Lebih lanjut, tampak bahwa perulangan yang sama dapat digunakan untuk menyelesaikan kedua masalah menggunakan pemrograman dinamis dengan perubahan yang sangat kecil (mengganti pengurangan dalam SS dengan divisi di SP).

Itu sampai saya membaca bab 8 "Theory of Computation" oleh Bernard Moret (bagi mereka yang tidak memiliki buku, ia memiliki bukti kekerasan produk subset melalui X3C - masalah yang sangat sulit NP).

Saya memahami pengurangan, tetapi tidak dapat menemukan apa yang salah dengan kesimpulan saya sebelumnya (ekuivalen dari dua masalah).

UPDATE : Ternyata produk subset hanya NP-complete lemah (produk target eksponensial dalam ). Gary dan Johnson menerbitkan ini di kolom NP-completeness mereka pada tahun 1981 , tapi saya kira itu kurang terlihat daripada klaim mereka sebelumnya dalam buku mereka. $\Omega (n)$

cc.complexity-theory np-hardness reductions subset-sum RDN
sumber

Mungkin akan lebih baik untuk membayangkan bagaimana Anda akan mengimplementasikan algoritma pemrograman dinamis Anda. Kemudian, Anda akan menemukan apa yang salah.

Yoshio Okamoto

@ MohammadAl-Turkistany: Ada di bagian akhir kolom

RDN

Jawaban:

Mengenai masalah kesetaraan Jumlah Subset dan Produk Subset Ada teknis tentang Subset Produk. Produk x's = T sebenarnya Psuedopolinomial jika T tidak eksponensial! Jadi bukti Subset Produk menjadi NP Hard tidak (karena alasan teknis !!!) cukup benar!

Namun diberi janji bahwa T Besar, maka pengurangan via Logaritma ke Subset Sum memberikan SUM SUBSET NON STANDAR yang melebihi real! Ini berarti bahwa algoritma Psuedopolynomial untuk Subset Jumlah Tidak berlaku! Meskipun Logaritma kecil, tempat desimal mengacaukan Pemrograman Dinamis Psuedopolinomial!

saya harap ini membantu

Zelah

Zelah 02
sumber

Ternyata Anda benar selama ini tentang pengurangan yang tidak benar (yaitu, mengklaim mereka menunjukkan kelengkapan NP yang kuat, ketika mereka tidak). Terima kasih!

RDN

Pertama, menggunakan eksponensial untuk beralih dari karya SS ke SP (menggunakan basis 2 daripada basis ), tetapi meledakkan ukuran angka yang terlibat. Kekerasan NP yang lemah berarti bahwa jika jumlahnya kecil (atau lebih tepatnya, dinyatakan dalam unary), masalahnya tidak lagi sulit. Oleh karena itu, menggunakan eksponensial membuat instance SP berukuran eksponensial bahkan untuk instance SS yang mudah, di mana angkanya ditulis dalam unary. $e$

Kedua, menggunakan logaritma untuk beralih dari SP ke SS tidak berfungsi, karena logaritma biasanya menghasilkan nilai non-integer. SS dan SP didefinisikan menggunakan angka integer, dan logaritma sering menghasilkan nilai transendental, yang sulit untuk diwakili atau dilakukan perhitungan matematika.

<edit>

Biarkan menjadi bilangan bulat, , lalu adalah rasional jika dan hanya jika adalah kekuatan 2, dan sebaliknya transendental. Pertama, jika $A$ $A > 0$ $\log_2 A$ $A$ untuk bilangan bulat bukan noldan, maka $\log_2 A = \frac{p}{q}$ $p$ $q$ ,. Karena itu kami memilikidengan dekomposisi prima. Selanjutnya, jadi dengan diberikita dapat memilihdanuntuk membuktikanadalah rasional. $A = 2^{\frac{p}{q}}$ $A^q = 2^p$ $A = 2^r$ $A^{rq} = 2^p$ $A$ $q=1$ $p=r$ $\log_2 A$

Kita hanya perlu menunjukkan bahwa tidak pernah transendental. Ini mengikuti dari teorema Gelfond-Schneider , untuk formulasi yang setara (seperti dapat ditemukan pada halaman Wiki) adalah "jika dan adalah bilangan aljabar bukan nol, dan kami mengambil logaritma bukan-nol dari , lalu bisa rasional atau transendental. " Juga mudah untuk memverifikasi dengan mengambil kebalikan dari teorema dan mengatur dan karenanya $\log_2 A$ $\alpha$ $\gamma$ $\alpha$ $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ $\alpha^\beta = \gamma$ $\beta = \log_\alpha \gamma$ .

</edit>

Lastly, consider what happens when we try the dynamic programming algorithm from SS on SP. Because we use products rather than sums, the numbers involved blow up enormously, and the arbitrary precision math required suddenly becomes a factor in the running time. This is why the algorithm cannot solve SP instances quickly even if the numbers are in unary.

Alex ten Brink
sumber

this leads to a somewhat interesting special case. for what class of numbers are the log's expressible as rationals and not requiring infinite precision? in this case the problems would indeed be nearly equivalent & reducible to each other. it also seems to lead toward a "natural" approximation algorithm.

vzn

Thanks for the great answer! I have just one issue -- I get why taking logs is illegal (except perhaps in the case where the logs are poly in length -- as vzn points out), but I'm still unsure about the legality of going from SS to SP via exponentiation. WRT going from SS to SP as you mentioned (via exponentiation), don't we run into the following problem: The number of bits in the input instance of

I_{S S}

$I_{SS}$ is

O (n \log x)

$O(n\log x)$ and the number of bits in the instance of

I_{S P}

$I_{SP}$ is

O (n x)

$O(nx)$ . This is an exponential blow-up. So is it still legal? If it is, why?

RDN

@vzn, RDN: I edited in a characterization when the logarithm is transcendental. About the blow-up in the reduction, it depends on your definition of 'legal': the reduction is correct, yet its efficiency is not polynomial, and hence does not say anything about NP-hardness. It is therefore not a correct poly-time reduction, but it is a correct reduction (without qualifiers).

Alex ten Brink

also there is a special case where all numbers are in the form

c^{n_{i}}

$c^{n_i}$ , each

n_{i}

$n_i$ rational, for any

c

$c$ , not just

c = 2

$c=2$ . the approximation algorithm I was thinking of might find a

c

$c$ such that the conversion of values into that "base" is "close" to the originals.

vzn

The literal explanation is that Subset Product problem is NP-complete by a reduction from strongly NP-complete problem such as exact cover by 3-sets. In such "strong" reduction, the input integers are bounded by some polynomial function in the number of integers in the resulting instance of Subset Product problem.

Such a "strong" reduction is impossible from any strongly NP-complete problem to Subset Sum Problem unless $P=NP$ . We have polynomial-time dynamic programming algorithm for solving Subset Sum problem if input integers are bounded by a polynomial.

Mohammad Al-Turkistany
sumber

Yes, I understand that. My question was about why the conclusion I had made earlier was incorrect (i.e., equivalence of SS and SP).

RDN

@rdn There are not equivalent in that sense unless P =NP.

Mohammad Al-Turkistany

Yes, I get that. But I want to know what was wrong with my reductions in either direction.

RDN

Can you outline you reductions?

Mohammad Al-Turkistany

Let

I (S S) = ⟨ X, S ⟩

$I(SS)=\langle X, S \rangle$ be an instance of SS and

I (S P) = ⟨ Y, P ⟩

$I(SP)=\langle Y, P \rangle$ be an instance of SP. Transforming

I (S S)

$I(SS)$ into

I (S P)

$I(SP)$ : Let

P = e^{S}

$P = e^S$ and

Y_{i} = e^{X_{i}}

$Y_i = e^{X_i}$ . There exists a SS of sum

S

$S$ iff there exists a SP of product

P = e^{S}

$P = e^S$ . Transforming

I (S P)

$I(SP)$ into

I (S S)

$I(SS)$ : Let

S = l o g (P)

$S = log(P)$ and

X_{i} = \log (Y_{i})

$X_i = \log(Y_i)$ . There exists a SP of product

P

$P$ iff there exists a SS of sum

S = \log (P)

$S = \log(P)$ .

RDN