The Complexity of Generalized Domino Tilings
The Complexity of Generalized Domino Tilings
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.