8
$\begingroup$

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
Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2012.07.11 $\endgroup$
    – Gerhard Paseman
    Commented Jul 11, 2012 at 13:15

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Cristopher Moore
    Commented Jul 15, 2012 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 16, 2012 at 10:17
  • $\begingroup$ Yes, I understand your second reduction now. And it uses all the tiles. Great! $\endgroup$
    – Cristopher Moore
    Commented Jul 16, 2012 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .