The Complexity of the Equation Solvability Problem over Finite Rings
Gábor Horváth, John Lawrence, Ross Willard · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2015
We investigate the complexity of the equation solvability problem over a finite ring when the input polynomials are written as sums of monomials. We prove that this problem can be solved in polynomial time for a finite ring if the factor by the Jacobson radical is commutative. It follows that for such rings the equivalence problem can be solved in polynomial time when the input polynomials are written as sums of monomials. This finishes the proof of the dichotomy theorems for the equivalence and equation solvability problems over finite rings.