I can prove Propp's problem is NP-complete for given finite set S of forbidden spacings and given finite N specified in binary, provided we are allowed to specify S by means of a formula using set operations (set union, intersection, subtraction, and minkowski sum). Actually the formula for S can consist wholy of set adjoinings and subtractions, provided we are allowed to include whole integer intervals as predefined sets. The proof is to show that the "max independent set" problem in a general graph G, which is NP-complete of course, can be encoded into a problem of Propp's form. Here is a sketch of how to prove it. One just selects random distances for the edges of G in such a way that the sum of signed distances going round a cycle, is always 0. It suffices to employ a "basic set" of cycles arising from a spanning tree plus 1 edge. These sum conditions are a linear system. Solve it by gaussian elimination. There will be a many-parameter set of solutions. Choose random values for the parameters. Result is rational distances, which can be made integer by scaling by a common denominator. With enough bits of randomness it becomes probable no two vertices of G will coincide on the number line and that no distance will be re-used. In other words for any finite graph G we can in this way in randomized polynomial time, embed G with vertices being integers and all edge (and non-edge intervertex) lengths distinct. Then the max independent set in G problem, is soluble by (1) asking for the edge lengths to be forbidden distances in Propp's problem, (2) the non-edge lengths are permitted distances, and (3) demanding that only integers corresponding to the vertices of G be used in F. Demand (3) can be enforced by adjoining a few extra vertices E to G and insisting all the unused integers in the interval (which are not G vertices) lie at forbidden distances to E (to do this we adjoin lots of forbidden distances). Finally we need to force it to include all of E in the max independent set, which we can do by making E consist of a large number of unconnected vertices. So really one needs to prove by Erdosian probabilistic method all this works, and fill in various details. But that all should be doable. This is only a proof sketch so I'm not. This proof will show that a well known NP-complete problem would be soluble in randomized polynomial time if Propp's problem were. Note this is only (what Garey & Johnson call) "weak" NP-hardness, not "strong" in the sense that if we demanded N be in unary then my proof would fail to show hardness. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)