Hardness of conjugacy, embedding and factorization of multidimensional subshifts

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>1 for subshifts of finite type and sofic shifts and in dimensions d≥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.