  We consider several computational problems related to conjugacy between
subshifts of finite type, restricted to $k$-block codes: verifying a proposed
$k$-block conjugacy, deciding if two shifts admit a $k$-block conjugacy, and
reducing the representation size of a shift via a $k$-block conjugacy. We give
a polynomial-time algorithm for verification, and show GI and NP-hardness for
deciding conjugacy and reducing representation size, respectively. Our approach
focuses on 1-block conjugacies between vertex shifts, from which we generalize
to $k$-block conjugacies and to edge shifts. We conclude with several open
problems.
