6
$\begingroup$

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, is NP-complete.

It is not hard to show that $\mathrm{TILING}$ is in NP.

How can I show that it is NP-Hard? Can I reduce some known language ($\mathrm{SAT}$, $\mathrm{3COL}$, $\mathrm{CLIQUE}$, etc) to it?

I have some idea of solution, similar to the proof of Cook-Levin theorem (to encode state of the Turing Machine), but it seems awkward to do it, since I have proved NP-Completeness of $\mathrm{SAT}$.

UPDATE:

  1. A "color set" is just some set, e. g. {6, 13, 42}, {1, 2, 3, ..., 200}, then a tile can look like (6, 6, 6, 13), (6, 13, 42, 6) for the first and (1, 2, 3, 4), (8, 8, 8, 8) for the second.
  2. Every neighbor side (order: up, left, down, right) must have the same color, but no restrictions for "outer" sides (edges), which doesn't have neighbors. And it's not possible to rotate tiles.Example
$\endgroup$
7
  • $\begingroup$ It is always "allowed" to directly prove that every NP machine reduces to your language, but it is usually easier to reduce from a known NP-complete problem. $\endgroup$ Dec 19 '21 at 11:08
  • 1
    $\begingroup$ Hi, what do you mean by "color set"? What exactly do you color? Also, how can the tiles in $T$ look like? $\endgroup$
    – nir shahar
    Dec 19 '21 at 17:53
  • $\begingroup$ @nirshahar, "color set" just some set, e. g. {6, 13, 42}, {1, 2, 3, ..., 200}, then a tile can look like (6, 6, 6, 13), (6, 13, 42, 6) for the first and (1, 2, 3, 4), (8, 8, 8, 8) for the second. $\endgroup$
    – Maxim
    Dec 19 '21 at 18:08
  • $\begingroup$ @Maxim, how would then the tiling look like? What significance does the coloring have (any restrictions on the coloring, for example)? $\endgroup$
    – nir shahar
    Dec 19 '21 at 18:30
  • 1
    $\begingroup$ @Maxim Please do not leave clarifications in the comments. Could you edit your question instead? It would be better for future visitors. Thanks! $\endgroup$ Dec 20 '21 at 16:26
4
$\begingroup$

Instead of $\mathsf{TILING}$, I proved that $\mathsf{RectangleTILING}$ is $\mathsf{NP}$-complete by finding a reduction from $\mathsf{3SAT}$.

Problem $\mathsf{RectangleTILING}$:

  • Input: a set $T$ of tiles, two dimensions $M$ and $N$ (in binary or unary, it doesn't matter);
  • Question: is it possible to cover a rectangle of size $N\times M$ with tiles of $T$?

If necessary, I will add some details to prove that $\mathsf{RectangleTILING}\leqslant_m^p\mathsf{TILING}$, but I think it is not that hard to prove.

I consider a 3-CNF boolean formula $\varphi = \bigwedge\limits_{i=0}^{m-1} C_i$ where $\forall i \in [\![0,m-1]\!]$, $C_i = (\ell_{i1}\vee \ell_{i2}\vee\ell_{i3})$ and $\ell_{ij}$ is either $x$ or $\overline{x}$ with $x\in\mathcal{V} = \{x_0,…,x_{n-1}\}$. I construct an input $(T, 3m, 2n)$ of $\mathsf{RectangleTILING}$ such that $\varphi$ is satisfiable if and only if it is possible to cover a rectangle of size $2n\times 3m$ with tiles of $T$.

Note that it is possible to encode coordinates for tiles using the colors. For example, the following tile could be put only on column $c$ and row $r$.

enter image description here

It is also possible to encode multiple informations in colors, using tuples. For readability purposes, I will chose to write tiles coordinates outside of colors.

Each tile will have only one choice of coordinates in the rectangle.

Now the idea is to use two rows per variable:

  • one row per variable $x_j$ will keep track of the boolean assignment chosen for $x_j$;
  • the other row will permit to know which variable satisfies each clause;

and three columns per clause:

  • one column per clause will sum up the boolean assignment of each variable;
  • one column will chose a variable to satisfy the clause;
  • the last column will pick a clause tile.

In details:

  • for $i$ from $0$ to $m-1$:
    • for $j$ from $0$ to $n-1$:
      • in coordinates $(2j, 3i)$, two possible tiles, encoding $x_j$ or $\overline{x_j}$: enter image description here

      • in coordinates $(2j, 3i+1)$:

        • for $k$ from $0$ to $n-1$, four tiles: enter image description here
      • in coordinates $(2j, 3i+2)$, two possible tiles, encoding $x_j$ or $\overline{x_j}$: enter image description here

      • in coordinates $(2j+1, 3i)$, encoding $x_j$ or $\overline{x_j}$, but no restriction on the left: enter image description here

      • in coordinates $(2j+1, 3i+1)$:

        • for $k$ from $0$ to $n-1$, four tiles same as $(3i+1, 2j)$, but the restriction on the right depends on the vertical color: enter image description here
      • in coordinates $(2j+1, 3i+2)$, if the clause $C_i$ is $(x\vee y\vee z)$ ($x$, $y$ and $z$ being litterals), then three possible tiles:

        enter image description here

Since the number of tiles is $(8n+9)mn$ and the dimension of the rectangle are $3m$ and $2n$, this input is constructible in polynomial time of the size of $\varphi$.

Now let us prove that the reduction is correct.

Suppose that $\varphi$ is satisfiable, and $\mu:\mathcal{V}\to \{0, 1\}$ a boolean assignment satisfying $\varphi$. Then it is possible to cover a rectangle of size $N\times M$ using tiles of $T$:

  • for coordinates $(2j, 3i)$, $(2j, 3i+2)$ and $(2j+1, 3i)$, choose the tile of the litteral of value $1$ for $\mu$;
  • for coordinates $(2j, 3i+1)$ and $(2j+1, 3i+1)$, choose the tile that can be put on the right of the previous one, with vertical color of a litteral satisfying the clause $C_i$;
  • for coordinates $(2j+1, 3i + 2)$, choose the only tile that can be put.

Conversely, if there is a possible tiling of a rectangle of size $N\times M$, then the first column gives a satisfying assignment of $\varphi$:

  • the row $2j$ has the same horizontal color and insures that a variable cannot have two boolean assignments;
  • the column $3i+1$ has the same vertical color, and the coordinates $(2i+1, 3i+2)$ has necessarily that same color (which is a satisfying litteral for $C_i$);
  • other tiles are for verification purposes.

Here's a possible tiling for the formula $(x_1\vee \overline{x_2}\vee x_4)\wedge (x_2 \vee x_3\vee \overline{x_4})$ (which is satisfiable). enter image description here

$\endgroup$
3
  • $\begingroup$ It's too detailed in fact :) Thank you $\endgroup$
    – Maxim
    Dec 20 '21 at 20:18
  • $\begingroup$ I think it's possible to directly reduce 3SAT just adding something like $(x \vee \overline{x} \vee x)$ $\endgroup$
    – Maxim
    Dec 20 '21 at 20:20
  • $\begingroup$ You can read the informal description before the details if you want to try it yourself! :-) $\endgroup$
    – Nathaniel
    Dec 20 '21 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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