The Complexity of the Equation Solvability Problem over Finite Rings

Horváth, Gábor and Lawrence, John and Willard, Ross (2015) The Complexity of the Equation Solvability Problem over Finite Rings. (Unpublished)

Text sigmasat.pdf Restricted to Registered users only Download (334kB) | Request a copy

Abstract

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.

Item Type:	Article
Subjects:	Q Science / természettudomány > QA Mathematics / matematika > QA72 Algebra / algebra Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User:	Dr Gábor Horváth
Date Deposited:	25 Sep 2015 16:50
Last Modified:	25 Sep 2015 16:50
URI:	http://real.mtak.hu/id/eprint/28210

Available Versions of this Item

• The Complexity of the Equation Solvability Problem over Finite Rings. (deposited 25 Sep 2015 16:50) [Currently Displayed]

Actions (login required)

Edit Item