Back to Search Start Over

Circuit Evaluation for Finite Semirings

Authors :
Ganardi, Moses
Hucke, Danny
König, Daniel
Lohrey, Markus
Publication Year :
2016

Abstract

The computational complexity of the circuit evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or multiplicative identity. The following dichotomy is shown: If a finite semiring is such that (i) the multiplicative semigroup is solvable and (ii) it does not contain a subsemiring with an additive identity $0$ and a multiplicative identity $1 \neq 0$, then the circuit evaluation problem for the semiring is in $\mathsf{DET} \subseteq \mathsf{NC}^2$. In all other cases, the circuit evaluation problem is $\mathsf{P}$-complete.<br />Comment: Some proof details from the previous version are simplified in the new version

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1602.04560
Document Type :
Working Paper