UCLA

For finite polyomino regions, tileability by a pair of rectangles is NP-complete for all but trivial cases yet can be solved in quadratic time for simply connected regions. Through a series of reductions and improvements, we construct a set of 117 rectangles for which the tileability of simply connected regions is NP-complete.

Tiling by dominoes in the plane is a matching problem, and thus can be solved in polynomial time. While the decision problem remains polynomial in higher dimensions, we prove that the counting problem becomes #P-complete. We also establish NP- and #P-completeness results for another generalization of domino tilings to higher dimensions.

We show that tileability of cofinite regions is undecidable, even for some fixed set of tiles, but present an algorithm for solving the case where all tiles are rectangular. We also show that whether a finite region can be enlarged by tiles such that the resulting region becomes tileable is also undecidable. Moreover, the existence of a tileable rectangle by a set of polyominoes is also shown to be undecidable.

It is not surprising that tiles can emulate other computational systems such as Turing machines and cellular automata. Some of these connections and consequences are explored and outlined. In particular, there are conjectures in the theory of cellular automata that, if proved, could lead to improvements of results in the theory of tilings.