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



one-dimensional (sort of) tilings
Yes, the problem is NP-complete. Here is a reduction of 1-in-3 SAT to your problem.


Let $\{C\_i:i< n\}$ be the given collection of 3-clauses in variables $\{x\_j:j< m\}$. All tiles and the region will have length $n+m+2$, so no shift is possible. For each of the $2m$ literals $a$ (which is $x\_j$ or $\neg x\_j$), we consider a tile of the form


$$1,\underbrace{0,\dots,0,1,0,\dots,0}\\_m,u\\_{a,0},\dots,u\\_{a,n-1},0,$$


where the $1$ in the left part appears at position $j+1$, and $u\_{a,i}$ is $1$ if $a$ occurs in $C\_i$, and $0$ otherwise. The region is


$$m,\underbrace{1,1,\dots,1}\_{n+m},0.$$


Note that the first and last number prevent reversal from being used. Then the left part forces any possible sum to use exactly one of the two literals $x\_j$, $\neg x\_j$ for any $j$, and the right part ensures that each clause is satisfied by exactly one of the selected literals.


Another variant of the reduction is that we consider tiles and the region of length $2n$; for each $j< m$, we take the tile


$$u\_{x\_j,0},u\_{x\_j,1},\dots,u\_{x\_j,n-1},u\_{\neg x\_j,n-1},u\_{\neg x\_j,n-2},\dots,u\_{\neg x\_j,0},$$


and the region is


$$\underbrace{1,1,\dots,1}\\_{n},\underbrace{2,2,\dots,2}\\_{n}.$$


Again, no shift is possible. Moreover, any solution must use all of the tiles, so the only choice is whether we reverse a given tile or not, which selects the variable assignment.


