Article contents
THE COMPLEXITY OF THE EQUIVALENCE PROBLEM OVER FINITE RINGS
Published online by Cambridge University Press: 09 December 2011
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
We investigate the complexity of the equivalence problem over a finite ring when the input polynomials are written as sum of monomials. We prove that for a finite ring if the factor by the Jacobson radical can be lifted in the centre, then this problem can be solved in polynomial time. This result provides a step in proving a dichotomy conjecture of Lawrence and Willard (J. Lawrence and R. Willard, The complexity of solving polynomial equations over finite rings (manuscript, 1997)).
- Type
- Research Article
- Information
- Copyright
- Copyright © Glasgow Mathematical Journal Trust 2011
References
REFERENCES
1.Burris, S. and Lawrence, J., Term rewrite rules for finite fields, Int. J. Algebr. Comput. 1 (1991), 353–369.CrossRefGoogle Scholar
2.Burris, S. and Lawrence, J., The equivalence problem for finite rings, J. Symb. Comp. 15 (1993), 67–71.CrossRefGoogle Scholar
3.Hazewinkel, M., Gubareni, N. and Kirichenko, V. V., Algebras, rings and modules, vol. 1 (Springer, New York, 2004).Google Scholar
4.Horváth, G., Lawrence, J., Mérai, L. and Szabó, Cs., The complexity of the equivalence problem for non-solvable groups, B. Lond. Math. Soc. 39 (3) (2007), 433–438.CrossRefGoogle Scholar
5.Hunt, H. and Stearns, R., The complexity for equivalence for commutative rings, J. Symb. Comp. 10 (1990), 411–436.CrossRefGoogle Scholar
6.Lawrence, J. and Willard, R., The complexity of solving polynomial equations over finite rings (manuscript, 1997).Google Scholar
9.Szabó, Cs. and Vértesi, V., The equivalence problem over finite rings, Internat. J. Algebra Comput. 21 (3) (2011), 449–457.Google Scholar
You have
Access
- 6
- Cited by