Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655439 | Journal of Combinatorial Theory, Series A | 2013 | 13 Pages |
Abstract
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 106 rectangles 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Igor Pak, Jed Yang,