Complexity of Some Problems in Module Algebra

摘要

The complexity of some relations on signatures and modules is established. The Signature Isomorphism Problem and the Module Isomorphism Problem are shown to be equivalent (with respect to polynomial time reductions) to the Graph Isomorphism Problem, whereas the Module Biinterpretation Problem and the Module Total Biinterpretation Problem are shown to be NP-complete.