This thesis looks at the complexity of isomorphism in two fairly distinct areas of mathematics.

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

Second, we consider isomorphism between quotients of centrally indecomposible genus 2 p-groups. We show isomorphism between quotients of such groups by non-central subgroups can be determined in polynomial time. The centrally indecomposible genus 2 groups split into two cases: flat and sloped [20]. We give a polynomial-time algorithm which correctly decides isomorphism between quotients of the flat genus 2 groups H^♭₁ (F_q) by central subgroups whenever the algorithm succeeds; we believe the algorithm always succeeds and have tested it on tens of millions of random examples. We again highlight several open problems.