Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.
Bibliographical noteFunding Information:
I am grateful to my advisor Igor Pak for proposing these problems, helpful conversations, reading this paper, and providing invaluable feedback. I also thank the anonymous referees for attentive reading of the paper and useful comments. The work is supported by the NSF under Grant No. DGE-0707424 .