2000/03/06 by Cristopher Moore, Moore, Cristopher, John Michael Robson +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0003039
arxiv created 2000/03/06 · openalex publication_date 2000/03/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.