reductionnpnp-completesubset-sumcomputability

Subset sum where the size of the subset is `k` is NPC?

I have a variation of Subset-Sum problem where the size of the subset is k and all the integers are positive (not zero).

As can be seen online, this question can be fairly solved using dynamic programming in pseudo-polynomial time.

I need to decide wether this problem is NPC, or in P (while assuming P!=NP).

I've tried to reduce from subset-sum problem, but had a problem with the constraint that all integers must be greater than zero. Since otherwise I would have just padded the input with k zero integers.

Formal definition of the problem:

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

Solution

  • 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)