Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles? In general this decision problem is undecidable for infinite regions and NP-complete for finite regions. It is sometimes easier to tile simply connected regions by using combinatorial group theory. Indeed, tiling simply connected finite regions by two rectangles can be solved in polynomial time. What about more rectangles?

In this talk, we will describe a set of rectangular tiles whose tileability problem is NP-complete for simply connected regions.

Joint work with Igor Pak.