Reports on Mathematical Logic

No. 31

Tomasz A. GORAZD,

The isomorphism testing for directly representable varieties

A b s t r a c t. Let $\cal V$ be a variety of algebras with a finite list of finite directly indecomposable members. We show that there is a polynomial time algorithm that tests the isomorphism between any two finite algebras from $\cal V.$ This includes the following classical structures in algebra:
Abelian groups with $nx=0$, $n>0$,
Boolean algebras,
Rings with $x^m=x$, $m>1$,
Modules over a finite semisimple ring.

Back to Main Menu