Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!cs.utexas.edu!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldors
From: halldors@paul.rutgers.edu (Magnus M Halldorsson)
Newsgroups: comp.theory
Subject: Re: An NP-Complete Problem?
Message-ID: <Mar.21.10.55.37.1990.18340@paul.rutgers.edu>
Date: 21 Mar 90 15:55:38 GMT
References: <637950193.627@minster.york.ac.uk>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 16

In article <637950193.627@minster.york.ac.uk> mike@minster.york.ac.uk writes:

> Given a get of tuples (bi, ci) and a value d, where
> the bi and ci are zero or positive integers, and d
> a non-zero positive integer, is it possible to test
> for the existance of a subset such that
> 
> sum bi <= d <= sum bi + sum ci

If the c_i's are all zero, then the problem reduces to finding a
subset such that
  sum b_i = d,
which is known as the Subset Sum problem and is NP-complete [e.g. see
Garey & Johnson pp.223].

Magnus