Counting complexity studies the resources needed to count solutions rather than merely decide whether a solution exists. The class 
consists of functions counting
the accepting computation paths of polynomial-time
nondeterministic Turing machines (Valiant 1979).
The class 
permits nondeterministic computation time 
, where 
is a polynomial in input length
.
The subclass 
permits time 
.
A counting problem is 
-complete under polynomial-time
metric reductions when it belongs to 
and every function in that
class can be computed by a polynomial-time transformation
of the input, one evaluation of the counting function,
and polynomial-time postprocessing of the input
and answer. The output is written in binary, and the postprocessing cost is measured
in the lengths of its inputs.
Chen and Xie (2026) give a fixed finite family of connected polyominoes for which counting translation-only tilings of an
square, with 
supplied in binary, is 
-complete under these reductions. Its counting function
belongs to 
.
The fixed tile set and binary encoding are essential
parts of the statement.
