  The classical Domino problem asks whether there exists a tiling in which none
of the forbidden patterns given as input appear. In this paper, we consider the
aperiodic version of the Domino problem: given as input a family of forbidden
patterns, does it allow an aperiodic tiling? The input may correspond to a
subshift of finite type, a sofic subshift or an effective subshift.
arXiv:1805.08829 proved that this problem is co-recursively enumerable
($\Pi_0^1$-complete) in dimension 2 for geometrical reasons. We show that it is
much harder, namely analytic ($\Sigma_1^1$-complete), in higher dimension: $d
\geq 4$ in the finite type case, $d \geq 3$ for sofic and effective subshifts.
The reduction uses a subshift embedding universal computation and two
additional dimensions to control periodicity. This complexity jump is
surprising for two reasons: first, it separates 2- and 3-dimensional subshifts,
whereas most subshift properties are the same in dimension 2 and higher;
second, it is unexpectedly large.
