In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two bars is NP-complete, except for a few trivial special cases. In a different direction, in 2005, Rémila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 106rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.
Bibliographical noteFunding Information:
We are grateful to Alex Fink, Jeff Lagarias, Leonid Levin, Cris Moore, Günter Rote, and Damien Woods for helpful conversations at various stages of this project. We also thank the anonymous referees for attentive reading of the paper and useful comments. The first author is partially supported by the NSF and BSF grants. The second author is supported by the NSF under Grant No. DGE-0707424 .
Copyright 2013 Elsevier B.V., All rights reserved.