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.ISAAC.2020.12
URN: urn:nbn:de:0030-drops-133568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13356/
Go to the corresponding LIPIcs Volume Portal

Alcock, Leo ; Asif, Sualeh ; Bosboom, Jeffrey ; Brunner, Josh ; Chen, Charlotte ; Demaine, Erik D. ; Epstein, Rogers ; Hesterberg, Adam ; Hirschfeld, Lior ; Hu, William ; Lynch, Jayson ; Scheffler, Sarah ; Zhang, Lillian

Arithmetic Expression Construction

pdf-format:
LIPIcs-ISAAC-2020-12.pdf (0.6 MB)

Abstract

When can n given numbers be combined using arithmetic operators from a given subset of {+,-,×,÷} to obtain a given target number? We study three variations of this problem of Arithmetic Expression Construction: when the expression
(1) is unconstrained;
(2) has a specified pattern of parentheses and operators (and only the numbers need to be assigned to blanks); or
(3) must match a specified ordering of the numbers (but the operators and parenthesization are free).
For each of these variants, and many of the subsets of {+,-,×,÷}, we prove the problem NP-complete, sometimes in the weak sense and sometimes in the strong sense. Most of these proofs make use of a rational function framework which proves equivalence of these problems for values in rational functions with values in positive integers.

BibTeX - Entry

@InProceedings{alcock_et_al:LIPIcs:2020:13356,
  author =	{Leo Alcock and Sualeh Asif and Jeffrey Bosboom and Josh Brunner and Charlotte Chen and Erik D. Demaine and Rogers Epstein and Adam Hesterberg and Lior Hirschfeld and William Hu and Jayson Lynch and Sarah Scheffler and Lillian Zhang},
  title =	{{Arithmetic Expression Construction}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13356},
  URN =		{urn:nbn:de:0030-drops-133568},
  doi =		{10.4230/LIPIcs.ISAAC.2020.12},
  annote =	{Keywords: Hardness, algebraic complexity, expression trees}
}

Keywords: Hardness, algebraic complexity, expression trees
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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