# Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

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?

-

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.

-
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. –  user46976 Feb 16 at 4:56
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. –  Joel David Hamkins Feb 16 at 4:58
Really grateful for your prompt answer :) –  user46976 Feb 16 at 4:59