Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP
Newsgroups: ut.theory
Subject: A problem
Message-ID: <4550@utcsri.UUCP>
Date: Fri, 10-Apr-87 07:05:52 EST
Article-I.D.: utcsri.4550
Posted: Fri Apr 10 07:05:52 1987
Date-Received: Sat, 11-Apr-87 13:09:31 EST
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 34

From: "VICTOR S. MILLER" <VICTOR@ibm.com>
Subject: A problem
     
Does anyone know anything about the following problem?
     
Inputs:
   A positive integer m, written in unary.
and a residue a mod m
     
Outputs:
   Call a subset S of Z mod m a-good if the sum of no non-empty subset
of S is = a.  The output is to be the cardinality of the largest good
subset (in the first version), or one such subset (in the second version).
Questions:
     
given a subset S is there a short proof that it is good (more
specifically, is the first problem in NP)?  Is there a good algorithm
(for either version).
     
Notes:
     
1) If a is relatively prime to m, then it is easy to show that there is
a good set of cardinality at least 2*r+1, where r is the integer
satisfying r**2-r <= 2*m-4 < r**2+r.  This value is about sqrt(2*m).
Namely we can obviously multiply everything by anything invertible mod
m, so that we can take a=m-1.  Take the subset S to be integers (or
residue classes) -k through k. Then any sum will be bounded in absolute
value by k*(k-1)/2 (the factor of 2 due to Don Coppersmith).
     
2) If l is a prime dividing m and a is relatively prime to l, then the
subset consisting of all residues divisible by l is a-good.  Thus, in
this case the cardinality is at least m/l.
     
3) How many a-good subsets are there of a given cardinality?