Hardness of conjugacy, embedding and factorization of multidimensional subshifts

•Knowing whether two SFTs of dimension higher than two are conjugate or if one embeds in the other is Σ10-complete.•Deciding whether one of two multidimensional SFTs, effective or sofic shifts factor onto the other is Σ30-complete.•For effective subshifts, all the results are also true in dimension one.

Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts in dimensions d>1d>1 for subshifts of finite type and sofic shifts and in dimensions d≥1d≥1 for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are Σ30-complete for sofic and effective subshifts and that they are Σ10-complete for SFTs, except for factorization which is also Σ30-complete.