On the complexity of finite sorted algebras

The general problem of testing the isomorphism of two given finite algebras is known to be isomorphism complete, i.e. polynomially equivalent to the g raph isomorphism problem (GI). It is easy to see that this fact still holds when sorts are introduced. However, this isomorphism problem is relevant o nly for algebras (or interpretations) of a fixed signature, and in some cas es, according to the signature, is much simpler than the general problem. W e therefore establish exactly for which signatures is the associated isomor phism problem simpler than GI, and for which is it isomorphism complete, it turns out that for non-monadic signatures, this problem is isomorphism com plete just as is the case without sorts, while the classification of monadi c signatures is more complex and interesting in the presence of sorts.