Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups

Details Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups

1997-11-03

arxiv.org/abs/math/9711224v1

Mathematics

Rings and Algebras

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity problems associated with matrix rings, matrix semigroups and Rees matrix semigroups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-62242