reduction - 子集大小为“k”的子集总和是 NPC？

Question

我有一个子集和问题的变体，其中子集的大小是k并且所有整数都是正数（不是零）。

从网上可以看出，这个问题可以用伪多项式时间内的动态规划来很好地解决。

我需要决定这个问题是NPC，还是在P（假设时P!=NP）。

我试图从子集和问题中减少，但遇到了所有整数必须大于零的约束问题。因为否则我只会用k零整数填充输入。

问题的正式定义：

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

Answer 1

The problem is in NPC.

If you could find polynomial time solutions to your problem then you could have polynomial time solutions to Subset Sum problem with upper bound Time of Subset Sum = k * (Your Problem's Time)

Answer 2

那个问题是NPC。​ 实际上，当 k 在 n ^{1- Ω (1)}时，即使是

所有数字都在 n ^O(k)
中，
并保证最多有一个解决方案

不怀疑将它无限地置于​CONT IME ( n^( o (k))) / 2 ^{o(k*n*log(n))}​中，
因为本文的定理证明 5.1给出了一个简化
：适用于这样的 k 并保留解决方案的数量。