Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.35
URN: urn:nbn:de:0030-drops-69978
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6997/
Ganardi, Moses ; Hucke, Danny ; König, Daniel ; Lohrey, Markus
Circuit Evaluation for Finite Semirings
| pdf-format: |
|
Abstract
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 R (i) has a solvable multiplicative semigroup and (ii) does not contain a subsemiring with an additive identity 0 and a multiplicative identity 1 != 0, then its circuit evaluation problem is in the complexity class DET (which is contained in NC^2). In all other cases, the circuit evaluation problem is P-complete.
BibTeX - Entry
@InProceedings{ganardi_et_al:LIPIcs:2017:6997,
author = {Moses Ganardi and Danny Hucke and Daniel K{\"o}nig and Markus Lohrey},
title = {{Circuit Evaluation for Finite Semirings}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {35:1--35:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6997},
URN = {urn:nbn:de:0030-drops-69978},
doi = {10.4230/LIPIcs.STACS.2017.35},
annote = {Keywords: circuit value problem, finite semirings, circuit complexity}
}
| Keywords: | circuit value problem, finite semirings, circuit complexity | |
| Seminar: | 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 06.03.2017 |
