J.Propp: One-dimensional packing of monomers with forbidden distances Given a finite set S of positive integers, and a positive integer N, let F(N,S) be the largest possible cardinality of a subset of {1,2,…,N} no two of whose elements differ by a number in S. What is known about the computational complexity of F? WDS: You can solve problems of this kind by "dynamic programming." Let T be the maximum member of S. The runtime and will be O(n)*C^T and the space usage O(C^T) for some constant C>1. For each n=1,2,....,N: tabulate the largest possible cardinality of a subset of {1,2,3,...,n} meeting both the forbidden distance conditions and the "boundary condition" specified by a given subset of {n+1, n+2, ..., n+T}. Note, each loop iteration's table is computed from previous table. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)