On the complexity of categoricity in computable structures
Walker M. White · Mathematical logic quarterly · 2003
Abstract We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Π11‐complete, while computable categoricity is Π04‐hard. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)