Consider the following one-dimensional tiling problem. Each "tile" is a sequence of nonnegative integers. A "region" is also such a sequence. I can shift the "tiles", or reverse them. A tiling is a set of shifted and/or reversed tiles that add up to the region. For instance, if my tiles are these three:

1 2

1 1 1

1 1 3

then I can tile the region

1 5 4 1

by adding up

1 1 1

_ 1 2

_ 3 1 1

Do you think this is NP-complete? Note that the tempting reduction from Subset Sum doesn't work; I want the inputs given in unary, so the numbers and the size of the region are polynomial.

• Cris Moore

Consider the following one-dimensional tiling problem. Each "tile" is a sequence of nonnegative integers. A "region" is also such a sequence. I can shift the "tiles", or reverse them. A tiling is a set of shifted and/or reversed tiles that add up to the region. For instance, if my tiles are these three:

1 2

1 1 1

1 1 3

then I can tile the region

1 5 4 1

by adding up

1 1 1

_ 1 2

_ 3 1 1

Do you think the decision problem of whether a given region can be tiled with a given set of tiles is is NP-complete? Note that the tempting reduction from Subset Sum doesn't work; I want the inputs given in unary, so the numbers and the size of the region are polynomial.

• Cris Moore