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.MFCS.2018.5
URN: urn:nbn:de:0030-drops-95874
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9587/
Go to the corresponding LIPIcs Volume Portal

Dose, Titus

Balance Problems for Integer Circuits

pdf-format:
LIPIcs-MFCS-2018-5.pdf (0.4 MB)

Abstract

We investigate the computational complexity of balance problems for {-,*}-circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010).
Our work shows that the balance problem for {-,*}-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable.
Starting from this result we precisely characterize the complexity of balance problems for proper subsets of {-,*}. These problems turn out to be complete for one of the classes L, NL, and NP.

BibTeX - Entry

@InProceedings{dose:LIPIcs:2018:9587,
  author =	{Titus Dose},
  title =	{{Balance Problems for Integer Circuits}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9587},
  URN =		{urn:nbn:de:0030-drops-95874},
  doi =		{10.4230/LIPIcs.MFCS.2018.5},
  annote =	{Keywords: computational complexity, integer expressions, integer circuits}
}

Keywords: computational complexity, integer expressions, integer circuits
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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