License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6997/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Hucke, Danny ; König, Daniel ; Lohrey, Markus

Circuit Evaluation for Finite Semirings

pdf-format:
LIPIcs-STACS-2017-35.pdf (0.5 MB)

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
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI