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

15

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={X1,...,Xn} et , est - il existe un sous - ensemble de telle sorte que .X i X x i = TTXjeXXje=T

Produit Subset: Étant donné et , ce qu'il existe un sous - ensemble tel que .T X i X x i = TX={X1,...,Xn}TXjeXXje=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.Ω(n)

RDN
la source
5
Il serait probablement bon d'imaginer comment vous implémenteriez votre algorithme de programmation dynamique. Ensuite, vous découvririez ce qui n'allait pas.
Yoshio Okamoto
@ MohammadAl-Turkistany: Son dans la dernière section de cette colonne
RDN

Réponses:

5

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

Zelah 02
la source
2
Il s'avère que vous avez toujours eu raison que les réductions étaient incorrectes (c.-à-d. Affirmant qu'elles montrent une forte complétude NP, alors qu'elles ne le font pas). Merci!
RDN
8

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 = pAA>0log2AA pour les entiers non nulspetq, alorsA=2 plog2A=pqpqA=2pq , . 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.Aq=2pA=2rArq=2pAq=1p=rlog2A

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 βlog2Aαγα(logγ)/(logα)=logαγαβ=γ .β=logαγ

</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.

Alex ten Brink
la source
cela conduit à un cas spécial quelque peu intéressant. pour quelle classe de nombres le log est-il exprimable en tant que rationnels et ne nécessitant pas une précision infinie? dans ce cas, les problèmes seraient en effet presque équivalents et réductibles les uns aux autres. il semble également conduire à un algorithme d'approximation "naturel".
vzn
1
Merci pour la bonne réponse! Je n'ai qu'un problème - je comprends pourquoi la prise de journaux est illégale (sauf peut-être dans le cas où les journaux sont de longueur poly - comme le souligne vzn), mais je ne suis toujours pas sûr de la légalité du passage de SS à SP via l'exponentiation. WRT allant de SS à SP comme vous l'avez mentionné (via l'exponentiation), ne rencontrons-nous pas le problème suivant: Le nombre de bits dans l'instance d'entrée de est O ( n log x ) et le nombre de bits dans le instance de I S P est O ( n x ) . Il s'agit d'une explosion exponentielle. Est-ce donc toujours légal? Si c'est le cas, pourquoi?ISSO(nlogx)ISPO(nx)
RDN
1
@vzn, RDN: J'ai édité une caractérisation lorsque le logarithme est transcendantal. Concernant l'explosion de la réduction, cela dépend de votre définition de `` légale '': la réduction est correcte , mais son efficacité n'est pas polynomiale, et donc ne dit rien sur la dureté NP. Ce n'est donc pas une réduction de poly-temps correcte , mais c'est une réduction correcte (sans qualificatifs).
Alex ten Brink
il y a aussi un cas spécial où tous les nombres sont sous la forme , chaque n i rationnel, pour tout c , pas seulement c = 2 . l'algorithme d'approximation auquel je pensais pourrait trouver un c tel que la conversion des valeurs dans cette "base" soit "proche" des originaux. cninicc=2c
vzn
1

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

Mohammad Al-Turkistany
la source
Oui, je comprends ça. Ma question était de savoir pourquoi la conclusion que j'avais faite plus tôt était incorrecte (c'est-à-dire l'équivalence de SS et SP).
RDN
@rdn Il n'y a pas d'équivalent dans ce sens sauf si P = NP.
Mohammad Al-Turkistany
Oui, je comprends. Mais je veux savoir ce qui n'allait pas avec mes réductions dans les deux sens.
RDN
Pouvez-vous décrire vos réductions?
Mohammad Al-Turkistany
Laissez - être une instance de SS et I ( S P ) = Y , P une instance du SP. Transformer I ( S S ) en I ( S P ) : Soit P = e S et Y i = e X i . Il existe un SS de somme S ssi il existe un SP de produitI(SS)=X,SI(SP)=Y,PI(SS)I(SP)P=eSYi=eXiS . Transformer I ( S P ) en I ( S S ) : Soit P ssi il existe un SS de somme S = log ( P ) . P=eSI(SP)I(SS) et X i = log ( Y i ) . Il existe un SP de produitS=log(P)Xi=log(Yi)PS=log(P)
RDN