Horváth, Gábor and Lawrence, John and Willard, Ross (2015) The Complexity of the Equation Solvability Problem over Finite Rings. (Unpublished)
This is the latest version of this item.
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 |