arvind@utcsri.UUCP (04/10/87)
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?