[math-fun] Propp's one-dimensional packing question
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)
Warren is quite right; I should have mentioned this in my post. My question is, can one do better than dynamic programming, for generic sets S? Jim Propp On Saturday, February 27, 2016, Warren D Smith <warren.wds@gmail.com> wrote:
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)
Perhaps an even more interesting question would be, what if the set S of forbidden spacings is infinite? In the case where S is finite, then the dynamic programming method shows that F grows linearly with N when N becomes large (if nonzero). But if S is infinite, for example S is the set of all positive squares, then the asymptotics of F(N,S) for large N become nonobvious, and the computational complexity also nonobvious. (Well, it wasn't obvious even for finite S, but at least a decent upper bound on that complexity was easy to see.) ------------------------- Now returning to the finite-S question, a totally different kind of attack is motivated by considering polynomials. Regard a set {A,B,C...} of nonnegative integers as being specified by the polynomial P(x)=x^A+x^B+x^C+... Now the condition that the polynomial P(x) be free of forbidden spacings from the set S, can be written in a number of ways. One is to note that P(x) * P(1/x) generates the set of spacings in P(x), along with their counts, e.g. a monomial A*x^B would mean "spacing B occurs A times." And P(x)*Q(x) where Q(x) is the generator polynomial for the set S, tells us forbidden locations for the next-larger element to add to the set F. If you wanted the distance D>0 to be forbidden, you could, e.g. demand that integral P(z)*P(1/z)*z^(-D-1) dz = 0 where the path of integration is a small circle surrounding 0. If you wanted the distances D in set S forbidden, demand Sum(D in S) |integral(round small circle) P(z)*P(1/z)*z^(-D-1) dz|^2 = 0. So then we have what looks more like a question in analysis rather than combinatorics. Is this polynomial trick of any use? I do not know. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
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)
participants (2)
-
James Propp -
Warren D Smith