The equivalence problem for finite rings (Q2366112): Difference between revisions

The equivalence problem (e.p.) for a ring is the problem of determining when two ring terms define the same function on the ring. Whereas \textit{H. B. Hunt} and \textit{R. E. Stearns} have earlier proved [ibid. 10, 411-436 (1990; Zbl 0724.68050)] for a finite ring \(R\) that: \(R\) is nilpotent implies the e.p. for \(R\) is in \(P\), -- \(R\) is non-nilpotent and commutative implies the e.p. for \(R\) is co-\(NP\)-complete; the present paper shows that the second of the above statements remains valid without the assumption of commutativity of \(R\). We note also the following result: Let \(R\) be a ring for which one can find a term \(f(x_ 1,x_ 2,\dots,x_ k)\) whose range is a nontrivial collection of central idempotent elements of \(R\). Then the e.p. for \(R\) is co-\(NP\)-hard.