Pak–Yang's three-rectangle NP-completeness conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.