27 Feb
2016
27 Feb
'16
8:54 a.m.
On Feb 26, 2016, at 11:09 PM, James Propp <jamespropp@gmail.com> wrote:
Responses to my MO post http://mathoverflow.net/questions/232165/one-dimensional-packing-of-monomers... haven't taught me anything.
Do any of you know (or can any of you figure out) how difficult packing problems of this kind are, from a complexity standpoint?
If S is held fixed, then F(n,S) is polynomial time, but that's not very interesting; I want to know what happens as S varies.
Jim Propp
A natural question, maybe not exactly what you are interested in, is the maximum density of the sequence (n -> infinity) for a given S. That can be calculated by working out a 2^K x 2^K transfer matrix, where K is one greater than the maximum forbidden distance. -Veit