文章基本信息

标题：Arithmetic Expression Construction
本地全文：下载
作者：Leo Alcock ; Sualeh Asif ; Jeffrey Bosboom 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-15
DOI：10.4230/LIPIcs.ISAAC.2020.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Hardness; algebraic complexity; expression trees