Computability Learning Seminar

Michael Gregory, University of Waterloo

The Complexity of the Isomorphism Problem for Finitely Generated Algebras

We review the arithmetic hierarchy and use it to analyze the isomorphism problem for finitely generated c.e. algebras. We introduce the ascending chain condition (ACC) on congruences and explain how it restricts the complexity of isomorphism. We show that any finitely generated c.e. algebra whose congruence lattice satisfies ACC has a \(\Pi_2\) isomorphism problem. Then, we prove that the class \(UF_2\) of algebras with two unary operations has \(\Sigma_3\)-complete isomorphism problem.

MC 5403