Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
share|improve this question
    
Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2012.07.11 –  Gerhard Paseman Jul 11 '12 at 13:15

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
In your first reduction, the tiling consists of half the tiles, namely those corresponding to the satisfying assignment --- right? The intent of my question was to use all the tiles (i.e. one copy of each one). Your second reduction uses all the tiles, but I'm confused: shouldn't the entire region consist of 1s? Where are there 2s in the second half? –  Cristopher Moore Jul 15 '12 at 17:02
    
I didn’t understand you want to use all the tiles. As for the second question: each tile contributes 1 in the left part to every clause where the corresponding true literal appears, and 1 in the right part to every clause where its negation appears. Thus the total in the left part counts the number of satisfied literals in each clause, and in the right part the number of unsatisfied literals. Since each clause has 3 literals and the assignment is supposed to satisfy exactly 1 of them, the number of unsatisfied literals is 2. –  Emil Jeřábek Jul 16 '12 at 10:17
    
Yes, I understand your second reduction now. And it uses all the tiles. Great! –  Cristopher Moore Jul 16 '12 at 19:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.