The complexity of the word-problem for finite matrix rings
Csaba Szabó, Vera Vértesi · Proceedings of the American Mathematical Society · 2004
We analyze the so-called word-problem for M 2 ( Z 2 ) M_2(Z_2) , the ring of 2 × 2 2\times 2 matrices over Z 2 Z_2 . We prove that the term-equivalence problem for the semigroup (and so for the ring) M 2 ( Z 2 ) M_2(Z_2) is coNP-complete.