9
$\begingroup$

Motivated by these following questions on tessellation:

coloring in lattice

Reference for Wang Tile

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

Could we actually show that the problem of trying to tile a finite size square with a given set of Wang tile to be NP-complete?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
11
$\begingroup$

If one considers the anchor-tile tiling problem, where the tiling must include a specified anchor tile, then indeed this problem is NP-complete. To see this, suppose that we have a given NP problem, where there is a polynomial time computable Turing machine $M$, such that we want to know on input $x$ whether there is some $y$ such that $M$ accepts $(x,y)$, and $M$ operates in polynomial time $p$ on any input. For any Turing machine, we have a canonical set of Wang tiles, with a specific anchor, such that the tilings extending this anchor correspond in a tight way to the operation of $M$ on a given input, allowing a tiling just in case the machine accepts the given input. If you understand how these tiles are constructed, so as exactly to mimic the operation of the Turing machine, then it is clear that we may also design the tiles so as to allow an arbitrary oracle input for the computation. So for any $x$, we can produce a set of tiles, such that they admit a tiling of the square $p(|x|)\times p(|x|)$ with the anchor if and only if there is some $y$ such that $M$ accepts $(x,y)$. In this way, we reduce the given NP problem to an instance of the tiling problem. So the anchor tiling problem of a given size must be NP complete.

I'm less sure of what happens when you do not insist on a given anchor tile, but perhaps this issue can be resolved as it is in the case of the halting problem, where one shows that the tiling problem even without anchors is equivalent to (the negation of) the halting problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry for my ignorance, does anchor tile restriction simply mean that "the input is a tile set and one element inside the set named "anchor" and "anchor" must be used and everything else is the same as basic Wang tile formalism"? Thank you. $\endgroup$
    – user46976
    Commented Feb 16, 2014 at 4:56
  • 1
    $\begingroup$ Yes. The anchor tile is simply one of the tiles, and the anchor tile problem is whether there is a tiling that uses that tile. The Turing machine encoding is easier to see for the anchor tile problem, since one can set up the simulation of the initial state of the computation using that anchor tile. $\endgroup$
    – Joel David Hamkins
    Commented Feb 16, 2014 at 4:58
  • $\begingroup$ Really grateful for your prompt answer :) $\endgroup$
    – user46976
    Commented Feb 16, 2014 at 4:59
14
$\begingroup$

You don't need an anchor tile. Jed Yang and I recently solved this on the way to stronger NP-completeness results (versions of this result were already known). We explain it all here. Similarly, the rectangular tileability problem is undecidable according to Yang's recent result here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Where is this in your paper? Here the underlying set must be a square and I can only find results related to general regions. $\endgroup$
    – domotorp
    Commented Apr 3, 2014 at 21:06
6
$\begingroup$

The problem is also trivially NP-complete without an anchor tile. The trick is that we can easily force any tile to become an anchor tile. First, take a set of tiles that have a unique way of tiling an $n\times n$ square, e.g., by putting (respectively matching) $(i,j)$'s on their sides where $1\le i,j\le n$. Then take the "direct product" of this tile set with, e.g., the tile set described by Joel except for the position where you want your anchor tile, there keep only that. This gives a suitable tile set.

ps. I used to give this as an exercise for undergrads and some of them always solved it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very good. But when you say "trivially NP-complete," I guess you are referring only to the nice reduction you have provided from the anchor-free case to the anchor case? I would call it easy, but I think of the NP-completeness argument, coding Turing machines, as nontrivial. $\endgroup$
    – Joel David Hamkins
    Commented Apr 3, 2014 at 23:35
  • $\begingroup$ @Joel: Yes, I meant that. $\endgroup$
    – domotorp
    Commented Apr 4, 2014 at 4:15

You must log in to answer this question.