arXiv:2610.42063 · v2

Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete

首次提交 2026-10-31 01:25

版本更新 2026-11-02 20:41

雷达观测 2026-11-04 23:41

摘要

An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.