  Complexity problems associated with finite rings and finite semigroups,
particularly semigroups of matrices over a field and the Rees matrix
semigroups, are examined. Let M_nF be the ring of n x n matrices over the
finite field F and let T_nF be the multiplicative semigroup of n x n matrices
over the finite field F. It is proved that for any finite field F and positive
integer n >= 2, the polynomial equivalence problem for the T_n F is
co-NPcomplete, thus POL-EQ_\Sigma(M_n F) (POL-EQ_\Sigma is a polynomial
equivalence problem for which polynomials are presented as sums of monomials)
is also co-NP-complete thereby resolving a problem of J. Lawrence and R.
Willard and completing the description of POL-EQ_\Sigma for the finite simple
rings. In connection with our results on rings, we exhibit a large class of
combinatorial Rees matrix semigroups whose polynomial equivalence problem is
co-NP-complete. On the other hand, if S is a combinatorial Rees matrix
semigroup with a totally balanced structure matrix M, then we prove that the
polynomial equivalence problem for S is in P. Fully determining the complexity
of the polynomial equivalence problem for combinatorial Rees matrix semigroups
may be a difficult problem. We describe a connection between the polynomial
equivalence problem for combinatorial Rees matrix semigroups and the retraction
problem RET for bipartite graphs, a problem which computer scientists suspect
may not admit a dichotomy into P and NP-complete problems (assuming P is not
equal to NP).
