Conjecture on hard square tiling enumeration
Statement
Let be a finite set of polyomino tiles on the square grid, with copies restricted to parallel translations. A tiling of with is a covering by translated tiles without overlap. The class consists of counting problems for objects verifiable in exponential time.
Square-tiling hardness conjecture. There exists a finite set of tiles such that counting the number of tilings of with is -complete.
This conjecture predicts exponential-hierarchy counting hardness even for square regions and a fixed tile set. The surrounding discussion emphasizes known hardness for general and slim regions, but gives no proof of the square-region claim.
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.