Re: Subset Sum Problem


JeffCameron wrote:
> While reading about the so-caled subset sum problem, I have encountered
> two different versions of the problem:
>
> 1) Given a set of integers, does there exist a subset that sums to some
> integer s?
>
> 2) Given a set of *positive* integers S, does there exist a subset that
> sums to s?
>
> I have read that (1) is NP-Complete. However, I do not know whether or
> not (2) is NP-Complete. does anyone know whether (2) is NP-Complete?

Yes, the "standard" reductions from 3-SAT to SubsetSum involve
only positive integers. So both versions are definitely NP-complete.

.

Relevant Pages

  • Subset Sum Problem
    ... While reading about the so-caled subset sum problem, ... Given a set of integers, does there exist a subset that sums to some ... I have read that is NP-Complete. ...
    (comp.theory)
  • Re: Subset Sum Problem
    ... => Merkle-Hellman knapsack system and its variants are all insecure." ... => describes the Subset Sum Problem (i.e. from a given set of numbers, ... The subset sum problem is NP-complete; ... Merkle-Hellman depended on disguising a simple special case. ...
    (sci.crypt)