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