Somme de sous-ensemble vs produit de sous-ensemble (dureté NP forte ou faible)

J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile.

Somme Sous - ensemble: Étant donné $X = \{x_1,...,x_n\}$ et , est - il existe un sous - ensemble de telle sorte que .X ′ ∑ i ∈ X ′ x i = $T$$X'$$\sum_{i\in X'}x_i = T$

Produit Subset: Étant donné et , ce qu'il existe un sous - ensemble tel que .T X ′ ∏ i ∈ X ′ x i = $X = \{x_1,...,x_n\}$$T$$X'$$\prod_{i\in X'}x_i = T$

J'ai toujours pensé que les deux problèmes étaient équivalents - une instance de SS pouvait être transformée en une instance de SP via l'exponentiation et une instance de SP en SS via des logarithmes. Cela m'a amené à conclure qu'ils appartenaient tous deux à la même classe de NP-dur - c'est-à-dire qu'ils étaient tous deux faiblement NP-durs.

De plus, il semble que la même récurrence pourrait être utilisée pour résoudre les deux problèmes en utilisant la programmation dynamique avec un très petit changement (en remplaçant la soustraction en SS par la division en SP).

C'était jusqu'à ce que je lise le chapitre 8 de "Theory of Computation" de Bernard Moret (pour ceux qui n'ont pas le livre, il a une preuve de la dureté du produit du sous-ensemble via X3C - un problème fortement NP-difficile).

Je comprends la réduction, mais je ne peux pas comprendre ce qui n'allait pas avec ma conclusion précédente (équivalence des deux problèmes).

MISE À JOUR : Il s'avère que le produit du sous-ensemble n'est que faiblement NP-complet (le produit cible est exponentiel dans ). Gary et Johnson ont publié cela dans leur colonne NP-exhausteness en 1981 , mais je suppose que c'était moins visible que leur affirmation précédente dans leur livre.$\Omega (n)$

Concernant le problème de l'équivalence de la somme du sous-ensemble et du produit du sous-ensemble Il existe une technicité concernant le produit du sous-ensemble. Le produit de x = T est en fait Psuedopolynomial si T n'est pas exponentiel! Les preuves que le produit Subset est NP Hard ne sont donc pas (pour des raisons techniques !!!) tout à fait correctes!

Cependant, étant donné la promesse que T est grand, la réduction via les logarithmes à la somme de sous-ensemble donne une somme de sous-ensemble non standard qui est supérieure aux réels! Cela signifie que l'algorithme Psuedopolynomial pour le sous-ensemble Sum ne s'applique pas! Bien que les logarithmes soient petits, la décimale gâche la programmation dynamique pseudo-polynomiale!

J'espère que ça aide

Zelah

Premièrement, utiliser l'exponentiation pour passer de SS à SP fonctionne (en utilisant la base 2 plutôt que la base ), mais fait exploser la taille des nombres impliqués. Une faible dureté NP signifie que si les nombres sont petits (ou plus précisément, notés en unaire), le problème n'est plus difficile. Par conséquent, l'utilisation de l'exponentiation crée des instances de SP de taille exponentielle même pour les instances faciles de SS, où les nombres sont écrits en unaire.$e$

Deuxièmement, l'utilisation de logarithmes pour passer de SP à SS ne fonctionne pas, car les logarithmes génèrent généralement des valeurs non entières. SS et SP sont définis à l'aide de nombres entiers, et les logarithmes entraînent souvent des valeurs transcendantales, difficiles à représenter ou à calculer.

<edit>

Soit un entier, A > 0 , alors log 2 A est rationnel si et seulement si A est une puissance de 2, et transcendantal sinon. Premièrement, si log 2 A = $A$$A > 0$$\log_2 A$$A$ pour les entiers non nulspetq, alorsA=2$\log_2 A = \frac{p}{q}$$p$$q$$A = 2^{\frac{p}{q}}$ , . On a donc que A = 2 r par décomposition première. De plus, A r q = 2 p , donc étant donné un A, nous pouvons choisir q = 1 et p = r pour prouver que log 2 A est rationnel.$A^q = 2^p$$A = 2^r$$A^{rq} = 2^p$$A$$q=1$$p=r$$\log_2 A$

Il suffit de montrer que le n'est jamais transcendantal sinon. Cela découle du théorème de Gelfond-Schneider , pour une formulation équivalente (comme on peut le trouver sur la page Wiki) est "si α et γ sont des nombres algébriques non nuls, et nous prenons tout logarithme non nul de α , alors ( log γ ) / ( log α ) = log α γ est soit rationnel, soit transcendantal. " Il est également facile à vérifier en prenant l'inverse du théorème et en posant α β = γ et donc $\log_2 A$$\alpha$$\gamma$$\alpha$$(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$$\alpha^\beta = \gamma$ .$\beta = \log_\alpha \gamma$

</edit>

Enfin, considérez ce qui se passe lorsque nous essayons l'algorithme de programmation dynamique de SS sur SP. Parce que nous utilisons des produits plutôt que des sommes, les nombres impliqués explosent énormément et les calculs de précision arbitraires requis deviennent soudainement un facteur dans le temps de fonctionnement. C'est pourquoi l'algorithme ne peut pas résoudre rapidement les instances SP même si les nombres sont unaires.

L'explication littérale est que le problème du produit de sous-ensemble est NP-complet par une réduction du problème fortement NP-complet tel que la couverture exacte par 3 ensembles. Dans une telle réduction "forte", les entiers d'entrée sont délimités par une fonction polynomiale du nombre d'entiers dans l'instance résultante du problème de sous-produit.

Une telle réduction « forte » est impossible de tout problème fortement NP-complet à Somme problème , sauf si Subset . Nous avons un algorithme de programmation dynamique en temps polynomial pour résoudre le problème de sous-ensemble si les entiers d'entrée sont délimités par un polynôme.$P=NP$