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.2017.33
URN: urn:nbn:de:0030-drops-80641
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8064/
Go to the corresponding LIPIcs Volume Portal

Barth, Dominik ; Beck, Moritz ; Dose, Titus ; Glaßer, Christian ; Michler, Larissa ; Technau, Marc

Emptiness Problems for Integer Circuits

pdf-format:
LIPIcs-MFCS-2017-33.pdf (0.5 MB)

Abstract

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT).

Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a major open problem in algebraic computing complexity:

1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007

2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006

3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010

BibTeX - Entry

@InProceedings{barth_et_al:LIPIcs:2017:8064,
  author =	{Dominik Barth and Moritz Beck and Titus Dose and Christian Gla{\ss}er and Larissa Michler and Marc Technau},
  title =	{{Emptiness Problems for Integer Circuits}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8064},
  URN =		{urn:nbn:de:0030-drops-80641},
  doi =		{10.4230/LIPIcs.MFCS.2017.33},
  annote =	{Keywords: computational complexity, integer expressions, integer circuits, polynomial identity testing}
}

Keywords: computational complexity, integer expressions, integer circuits, polynomial identity testing
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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