The Computational Complexity of Subclasses of Semiperfect Rings

This paper studies the computational complexity of subclasses of semiperfect rings from the perspective of computability theory. A ring is semiperfect if the identity can be expressed as a sum of mutually orthogonal local idempotents. Semisimple rings and local rings are typical subclasses of semiperfect rings that play important roles in noncommutative algebra. First, we define a ring to be semisimple if the left regular module can be decomposed as a finite direct sum of simple submodules and prove that the index set of computable semisimple rings is Σ20-hard within the index set of computable rings. Second, we define local rings by using equivalent properties of non-left invertible elements of rings and show that the index set of computable local rings is Π20-hard within the index set of computable rings. Finally, based on the Π20 definition of local rings, computable semiperfect rings can be described by Σ30 formulas. As a corollary, we find that the index set of computable semiperfect rings can be both Σ20-hard and Π20-hard within the index set of computable rings.