The Complexity of Generalized Domino Tilings

Igor Pak, Jed Yang

Abstract


Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial.  We prove a variety of hardness results (both NP- and #P-completeness) for different generalizations of dominoes in three and higher dimensions.

Keywords


tilings; dominoes; complexity

Full Text: PDF