Le problème de «produit de sous-ensemble» est-il NP-complet?

21

Le problème de sous-ensemble est un problème classique NP-complet:

Étant donné une liste de nombres et un cible , y a-t-il un sous-ensemble de nombres de qui se résume à ?LL kkLk

Un étudiant m'a demandé si cette variante du problème appelé problème de "produit de sous-ensemble" est NP-complète:

Étant donné une liste de nombres et une cible , existe-t-il un sous-ensemble de nombres de dont le produit est ?k L kLkLk

J'ai fait quelques recherches et je n'ai pas trouvé de ressources qui parlaient de ce problème, bien que peut-être je les ai manquées.

Le problème de produit du sous-ensemble est-il NP-complet?

templatetypedef
la source
2
Des réponses intéressantes, mais je me demande: ne pouvons-nous pas réduire à la somme des sous-ensembles simplement en prenant des journaux de k et de tous les nombres? (Peut-être que je devrais poser une question séparée?)
j_random_hacker
1
@j_random_hacker, oui, si vous ne trouvez pas de réponse après une recherche sur ce site et en ligne, je vous suggère de poser une question distincte. C'est une belle question avec une bonne réponse (indice: prendre des journaux vous laisse avec quelque chose qui n'est pas un entier; dans l'autre sens, pensez à ce que l'exponentiation fait à la taille des nombres), mais c'est un peu tangent et serait mieux dans sa propre question.
DW
1
@DW: Merci, quand j'aurai le temps, je ferai ce que vous proposez!
j_random_hacker

Réponses:

13

Un commentaire mentionne une réduction du X3C au PRODUIT SOUS-ENSEMBLE attribué à Yao. Étant donné l'objectif de la réduction, il n'était pas difficile de deviner quelle aurait été la réduction.

Définitions:

COUVERTURE EXACTE PAR 3 JEUX (X3C)

Étant donné un ensemble fini avec | X | un multiple de 3 et une collection C de sous-ensembles de 3 éléments de X , C contient-il une couverture exacte C ' pour XX|X|CXCCX , où et chaque élément de X se produit exactement une fois dans C ?CCXC

PRODUIT SOUS-ENSEMBLE

Étant donné une liste de nombres et une cible k , existe-t-il un sous-ensemble de nombres de L dont le produit est k ?LkLk

Pour réduire une instance X3C en une instance SUBSET PRODUCT:

  1. Etablir une cartographie bijective entre les membres de X et le premier nombres premiers. Remplacez les membres de X et des sous-ensembles C par les nombres premiers mappés.|X|XC

  2. Pour chaque sous-ensemble en , multipliez ses membres ensemble; la liste de produits résultante est L pour l'instance SUBSET PRODUCT. Étant donné que les nombres premiers sont utilisés pour le mappage à l'étape 1, les produits sont garantis équivalents si les sous-ensembles sont équivalents par le théorème de factorisation unique .CL

  3. Multipliez les membres de ensemble; le produit résultant est la valeur k de l'instance SUBSET PRODUCT.Xk

Les principaux facteurs de sont exactement les membres de X . Les facteurs premiers des nombres enkX correspondent exactement aux membres dessous-ensembles C. Par conséquenttoute solution à la nouvelle instance de produit de SUBSET peut être transformé en une solution de X3c en mappant les éléments desolution de L vers les sousensembles en C .LCLC

Chacune des 3 étapes de transformation implique des opérations polynomiales à la taille de l'entrée ou la taille d'un élément de X . Le premier | X | les nombres premiers peuvent être générés dans le temps O ( | X | ) à l'aide du tamis d'Ératosthène et sont garantis pour s'insérer dans O ( | X | 2 ln|X|X|X||X|espace | X | ) par lethéorème des nombres premiers.O(|X|2ln|X|)

Kyle Jones
la source
1
+1, mais pour que la réduction passe, je pense que nous devons que le premier | X | les nombres premiers peuvent être représentés par un nombre de bits polynomial dans | X | - ai-je raison à ce sujet, et si oui, avons-nous cette garantie?
j_random_hacker
1
Excellent point. J'ai ajouté un paragraphe pour répondre à cela.
Kyle Jones
1
Merci, ce théorème le cimente! Pas à la pique-nique, mais selon la page à laquelle vous avez lié, le kième nombre premier est approximativement k log k, et étant donné que le tamis d'Ératosthène calcule apparemment tous les nombres premiers jusqu'à n dans le temps O (n log log n) , en substituant n = k log k semble donner un temps de O (k * log (k) * log (log (k log k))), plutôt que O (k) (votre O (| X |)), pour calculer le premier k amorce de cette façon.
j_random_hacker
1
Kyle Jones, n'est-il pas essentiel que l'étape 3 crée un nombre de taille exponentielle? Cette réduction du temps polynomial est-elle vraiment? k
user1742364
3
@ user1742364 Non, car le calcul ne nécessite pas un nombre exponentiel d'opérations ou ne nécessite pas le stockage d'un nombre exponentiel de bits. L'informatique k nécessite | X | multiplications et multiplication est au pire une opération O ( n 2 ) . Alors que k sera exponentiellement plus grand que le plus grand P premier de X , le nombre de bits nécessaires pour stocker k sera O ( log P ) . kk|X|O(n2)kPXkO(logP)
Kyle Jones
9

Selon [ 1 ]: Oui c'est

Je cite également la même référence: Commentaires: Il y a une distinction technique subtile entre ceci et le problème 42: le premier cas a un algorithme pseudo-efficace obtenu en permettant aux nombres d'être représentés en unaire; sauf si tous les problèmes NP-complets peuvent être résolus par des algorithmes rapides, cependant, le problème de produit de sous-ensemble ne peut pas être résolu par des méthodes «efficaces» utilisant même cette représentation d'entrée déraisonnable.

jetez un oeil sur [2] pour une réduction. [2]: Fellows, Michael et Neal Koblitz. "Complexité et cryptographie à paramètres fixes." Algèbre appliquée, algorithmes algébriques et codes de correction d'erreur (1993): 121-131.

AJed
la source
1
Une réduction ou une citation réelle dans un article de revue serait bien, si possible.
templatetypedef
3
@templatetypedef A Garey et Johnson, la réduction est à la couverture exacte de 3 sets. En raison d'une communication privée avec Yao.
AJed
La réduction du papier de cryptographie est pour un problème différent, dans lequel le produit cible est remplacé par une congruence avec un nombre cible modulo un module donné dans l'instance. (Bien que si je comprends bien la preuve, ils n'obtiennent de toute façon qu'une faible dureté car le module est de magnitude exponentielle.)
Jeffrey Bosboom