Complexité d'une variante de somme de sous-ensemble

Cette variante du problème de somme de sous-ensemble est-elle facile / connue?

Étant donné un entier $m$ et un ensemble d'entiers positifs tels que chaque a au plus bits mis à ( ); existe-t-il un sous-ensemble tel que la somme de ses éléments soit égale à ?x i k = 2 1 x i = 2 b i 1 + 2 b i 2$A = \{x_1, x_2, ..., x_n\}$$x_i$$k=2$$1$A ′ ⊆ A $x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$$A' \subseteq A$$m$

Est-ce dans ? Est-il toujours terminé?N $\sf{P}$$\sf{NP}$

Et si chaque a au plus bits mis à ? Pour le problème est trivial. k = 3 1 k = $x_i$$k=3$$1$$k=1$

Il est toujours complet, même pour k = 2 . Étant donné une instance de somme de sous-ensemble, nous pouvons la transformer en cette variante en divisant les nombres et en ajoutant des bits supplémentaires.$\sf{NP}$$k=2$

Premièrement, la somme de tous les nombres dans le problème sera inférieure à pour une certaine valeur de m .$2^m$$m$

Maintenant, prenons un nombre du problème d'origine qui a défini k bits. Nous diviserons ce nombre en k nombres avec exactement 2 bits définis de telle sorte que la somme de ces nombres soit n + 2 k + m . Nous pouvons le faire récursivement, en trouvant des nombres ⌈ k ⌉ qui résument jusqu'aux premiers ⌈ k ⌉ bits plus 2 k + m - 1 et des nombres ⌊ k ⌋ qui résument jusqu'aux derniers ⌊ k ⌋ bits plus 2 $n$$k$$k$$n+2^{k+m}$$\lceil{k}\rceil$$\lceil{k}\rceil$$2^{k+m-1}$$\lfloor{k}\rfloor$$\lfloor{k}\rfloor$ .$2^{k+m-1}$

En plus de ce nombre, nous ajouterons également le nombre au problème. Une solution doit contenir ce nombre ou tous les k nombres construits précédemment. Si la valeur cible d'origine était t, la nouvelle valeur cible sera t + 2 k + m .$2^{k+m}$$k$$t$$t+2^{k+m}$

Si le problème d'origine avait plus d'un nombre, nous pouvons répéter ce processus en prenant pour la nouvelle valeur de m .$k+m+1$$m$

Il n'y a que deux façons de régler le bit à la position : la réponse peut contenir le nombre 2 k + m ou tous les k nombres qui résument jusqu'à n + 2 k + m . Nous avons donc réduit la somme de sous-ensemble à votre variante de somme de sous-ensemble.$k+m$$2^{k+m}$$k$$n+2^{k+m}$

Par exemple, prenons avec la valeur cible 7 . Ce problème pourrait être codé comme la variante de somme de sous-ensemble présentée ici en prenant les nombres binaires suivants:${\{2,3,5\}}$$7$

2 est mappé sur et 0000 1 . (L'utilisation du bit supplémentaire n'est pas strictement nécessaire ici.)$0100\ 1$$0000\ 1$

3 est mappé sur et 0000 00 $1000\ 00\ 1, 0100\ 00\ 1$$0000\ 00\ 01$

5 est mappé à et 0000 00 000 01 .$1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$$0000\ 00\ 000\ 01$

La nouvelle valeur cible deviendrait .$1110\ 10\ 010\ 01$

Si le problème d'origine est représenté avec bits, alors le problème transformé a au plus O ( n 4 ) bits. Le problème d'origine aura au plus O ( n ) nombres chacun avec au plus O ( n ) bits, donc la somme de tous sera également O (n). Le problème transformé aura O ( n 2 ) nombres (puisque chaque nombre à n bits est divisé en n + 1 nombres à 2 bits, leur longueur étant au plus O ( n 2$n$$O(n^4)$$O(n)$$O(n)$$O(n^2)$$n$$n+1$ $2$$O(n^2)$puisque nous utilisons bits supplémentaires pour chaque nombre. La taille totale du problème transformé est donc O ( n 4 ) bits.$n$$O(n^4)$

Il s'agit d'informations extraites de la question de Vor.

Pour le problème reste NP-complet. J'ai trouvé une réduction rapide de X-SAT monotone ( voir le schéma de la réduction ici ).$k \geq 3$

Le problème reste NP-complet même si , voir la réponse de Tom pour plus de détails. Voici une petite représentation de sa réduction de SUBSET SUM:$k = 2$