Pak–Yang's three-rectangle NP-completeness conjecture
Pak–Yang's three-rectangle NP-completeness conjecture
A rectangle tiling set is a finite set 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 . Pak–Yang's conjecture. There exists a set of rectangles such that tiling simply connected regions with 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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.