2026-07-23T03:47:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13356 2024-03-06T10:51:46Z ddc:004 open_access

Arithmetic Expression Construction 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 Hardness algebraic complexity expression trees 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 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 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.12 urn:nbn:de:0030-drops-133568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode