Subset Sum Problem

From: "JeffCameron" <cameron.jp@xxxxxxxxx>
Date: 15 Jan 2006 15:47:40 -0800

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?

If (2) is not NP-Complete, does there already exist an algorithm that
solves (2) in polynomial time?

Jeff Cameron

.

Follow-Ups:
- Re: Subset Sum Problem
  - From: Googmeister

Prev by Date: Re: 120,510,132 truth tables generated by 3-CNF of five variables [ttcnf]
Next by Date: Re: Subset Sum Problem
Previous by thread: Re: 120,510,132 truth tables generated by 3-CNF of five variables [ttcnf]
Next by thread: Re: Subset Sum Problem
Index(es):
- Date
- Thread

Relevant Pages

Re: Subset Sum Problem
... > While reading about the so-caled subset sum problem, ... > 1) Given a set of integers, does there exist a subset that sums to some ... > I have read that is NP-Complete. ... only positive integers. ...
(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)