La somme du sous-ensemble où la taille du sous-ensemble est `k` est NPC?

Question

J'ai une variation de Subset-Sum problem où la taille du sous-ensemble est k et tous les entiers sont positifs (pas zéro).

Comme on peut le voir en ligne, cette question peut être résolue de manière assez précise en utilisant la programmation dynamique en temps pseudo-polynomial. J'ai besoin de décider si ce problème est NPC, ou P

J'ai essayé de réduire le problème de la somme des sous-ensembles, mais j'ai eu un problème avec la contrainte que tous les entiers doivent être supérieurs à zéro. Depuis sinon je aurais simplement rembourré l'entrée avec k zéro entiers.

Définition formelle du problème:

L={<S1,S2,...,Sn,T,k>|There exists a subset I of S1,...,Sn of size m which sums up to T}

Answer 1

Le problème est PNJ.

Si vous pouviez trouver des solutions polynomiales à votre problème, vous pourriez avoir des solutions de temps polynomial au sous-ensemble problème Somme avec le temps majorant de Subset Somme = k * (temps de votre problème)

Answer 2

Ce problème est PNJ. En fait, lorsque k est égal à n ^{1- Ω (1)}, même la combinaison de

tous les chiffres étant en n ^{O (k)}
avec
le promise qu'il n'y a at most one solution

ne les soupçonne pas le mettre dans coN T IME (n^(o (k)))/2^{o(k*n*log(n))} infiniment souvent,
depuis this paper's Proof of Theorem 5.1 donne une réduction
qui fonctionne pour de tels k et préserve le nombre de solutions.