Computational complexity of \(k\)-block conjugacy (Q2219057)

The authors study the problem of deciding whether two given shifts of finite type are conjugate. They show that it can be decided in \(O(|V|^{4k})\) time if a \(k\)-block code from a vertex shift on \(V\) vertices to another vertex shift is a conjugacy, and a similar result holds for edge shifts. They provide a polynomial-time reduction from the 1-Block Conjugacy problem to the \(k\)-Block Conjugacy problem, and show that these problems are GI-hard (both for vertex shifts and edge shifts), which means that they have polynomial-time Turing reductions to the Graph Isomorphism problem. Moreover, the \(k\)-Block Reduction problem, which consists in finding a conjugacy to a vertex shift with smaller vertex set (by a fixed integer), is shown to be NP-complete for \(k=1\). The corresponding questions for edge shifts as well as for \(k > 1\) are open.