Metraipolis › archive › dc_1c219e4fdb71
Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete — arXiv:2610.42063
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42063
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-02T08:07:38.923Z
- SHA-256 of the archived text
3a740670d5354c68308b818028b486f7be204822b3bbe0ca934e445f8470f19d- Stable URL of this page
https://metraipolis.com/documento/dc_1c219e4fdb71
How to cite
Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete — arXiv:2610.42063 — arXiv (en), https://arxiv.org/abs/2610.42063 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1c219e4fdb71 (Metraipolis archive dc_1c219e4fdb71, sha256 3a740670d5354c68308b818028b486f7be204822b3bbe0ca934e445f8470f19d)
BibTeX
@misc{dc1c219e4fdb71,
title = {Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete — arXiv:2610.42063},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42063},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1c219e4fdb71; sha256 3a740670d5354c68308b818028b486f7be204822b3bbe0ca934e445f8470f19d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42063. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The gap between feasibility and exact counting raises a fundamental question about how much information an input must carry to sustain computational hardness. We show that this separation persists even when the geometric rules are fixed and each instance is specified solely by the binary side length of a square. Specifically, there exists a fixed finite family of connected polyominoes whose translation-only square-tiling counting function is #EXP-complete under polynomial-time metric reductions and belongs to #E. Since tileability for any fixed polyomino family is decidable in polynomial time, this result establishes a striking separation between feasibility and exact counting under highly restricted geometric inputs. The proof develops a two-stage numerical isolation technique that recovers accepting-computation counts from a boundary-amplified Wang system and preserves them through a rigid geometric compiler that controls all noncanonical polyomino tilings. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2610.42063 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-02T07:45:45.705Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).