Pak–Yang's three-rectangle NP-completeness conjecture

A rectangle tiling set is a finite set RR of rectangles, and a simply connected region is a region in the plane without holes that is to be tiled using translated copies of rectangles from RR. Pak–Yang's conjecture. There exists a set RR of 33 rectangles such that tiling simply connected regions with RR is \textsf{NP}-complete. This conjecture concerns the minimum size of a fixed rectangle set yielding computationally intractable tiling; the paper proves the corresponding result for a set of 111111 rectangles, while the three-rectangle case remains open.

Sources & referencesView supporting material

Primary source

Chao Yang and Zhujun Zhang, “NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles”, arXiv:2405.01017 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.