Complexity in Enumerative Combinatorics — Conjecture 4

Definitions and mathematical statement

Let $T$ be a fixed finite set of tiles. Write $[m\times n]$ for the rectangular board of dimensions $m$ and $n$, and let \[ g_T(m,n)=\#\{\text{tilings of }[m\times n]\text{ by tiles from }T\}. \] A tiling covers the board without gaps or overlapping tile interiors, using the placements permitted by the tile model. The supplied excerpt does not specify that model, the permitted transformations of tiles, or the boundary conventions. Thus this definition remains dependent on those choices; in particular, it does not assume that the tiles are polyominoes or that rotations and reflections are permitted. The admissible integer dimensions and treatment of zero dimensions are also not stated.

For a function on finite input strings, $\#\mathrm{EXP}$ denotes the class of functions counting accepting computation paths of nondeterministic machines running in time at most $2^{p(\ell)}$, where $\ell$ is the input length and $p$ is a polynomial. Completeness requires membership in this class and hardness under a specified reduction convention.

Conjecture 4 (Pak, 2018; formulation supplied by the registry). There exists a finite tile set $T$, fixed independently of the board dimension, such that the function \[ F_T(n)=g_T(n,n) \] is $\#\mathrm{EXP}$-complete.

The excerpt does not specify how $n$ is encoded or which reductions define completeness. Consequently, this is a conjectural formulation with unresolved complexity conventions, rather than a fully specified counting problem. No input encoding or reduction convention is imposed here.

The source also asks, for fixed $T$, whether $g_T(m,n)$ is computable in polynomial time. Its input encoding, output representation, and size parameter are unspecified. The source presents the conjecture as suggesting a negative answer; this draft preserves that motivation without asserting an unconditional separation of complexity classes.

Short English statement

Pak's supplied Conjecture 4 asserts that some fixed finite tile set makes counting tilings of square boards $\#\mathrm{EXP}$-complete. The tile model, boundary rules, input encoding, and reductions must be clarified before this becomes a precise complexity statement. The accompanying question asks whether rectangular-board tiling counts can be computed in polynomial time.

Sources

• Local UnsolvedMath registry, permanent ID $800320$, exact source problem code catalogue entry, title "Complexity in Enumerative Combinatorics --- Conjecture 4." The supplied record attributes the conjecture to Pak, with proposed year 2018, and labels it open. That label is supplied registry metadata, not an independently verified mathematical or literature assessment.
• Supplied source reference: Pak, Complexity Problems in Enumerative Combinatorics (2018), Conjecture 4, https://arxiv.org/abs/1803.06636. The background records access on 2026-10-16 and extraction method arxiv_latex. These are supplied provenance details; no source visit or independent verification is claimed here.