Motivated by these following questions on tessellation:


[coloring in lattice](https://mathoverflow.net/questions/147374/coloring-in-lattice)


[Reference for Wang Tile](https://mathoverflow.net/questions/149565/reference-for-wang-tile)


[Computational approach deciding whether a set of Wang Tile could tile the space up to some size](https://mathoverflow.net/questions/157239/computational-approach-deciding-whether-a-set-of-wang-tile-could-tile-the-space)


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?



Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
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. 


