# For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply connected region with these rectangle shapes is NP-complete. However the number of rectangle shapes $10^6$ seems pretty extreme. Maybe it's hard to close the gap on P vs. NP-complete for tiling in terms of the number of rectangle shapes available, but what if we allow more complex pieces such as non-rectangular Tetris pieces and larger non-rectangular pieces? (We could insist the piece shapes are all simply connected, but I'm not adamant about that).

Can we show NP-completeness for tiling a simply connected region with a much smaller set of (potentially non-rectangular) pieces available, compared to $10^6$?

The authors mention and rely upon an NP-completeness result for tiling with "Generalized Wang Tiles" that seem to use coloring as well as shape, and claim that NP-completeness can be achieved with a fixed set of 23 generalized Wang tiles. However I wasn't able to decipher this result to figure out how many ordinary non-colored (and e.g., perhaps also simply connected) tile shapes are needed to establish NP-completeness.

• Is showing that a certain class of simply-connected regions is NP-complete (e.g. all $(2, m)$ rectangles) enough, or must the selected set of pieces be NP-complete for all simply-connected regions?
– orlp
Sep 19, 2015 at 17:08
• @orlp According to how I was taught, if the problem is NP-complete for a subclass of problem instances then it is NP-complete overall (as long as there is no dramatic input size reduction of the problem for the subclass), although some other subclasses may be easy. So if hardness can be shown for tiling of $2 \times m$ rectangle regions for a certain fixed set of tiling pieces, in my book that would definitely qualify. But the input size would have to be more like $O(m)$, not $O(\log m)$, since the encoding of an arbitrary simply connected region is proportional to the number of unit squares. Sep 19, 2015 at 17:21
• @orlp However I should say, although it wasn't my original intent, if NP-completeness can be shown for $2 \times m$ regions with a fixed set of tile shapes when the input size of the region to be tiled is considered to be $O( \log m)$, that would still be interesting -- just not what I originally intended. Sep 19, 2015 at 17:28