论文标题
算术表达构建
Arithmetic Expression Construction
论文作者
论文摘要
$ n $何时可以使用$ \ {+， - ， - \ times，÷\} $的算术运算符组合给定数字？我们研究了算术表达构建问题的三种变化：当表达（1）不受限制时； （2）具有指定的括号和操作员模式（只有数字需要分配给空白）；或（3）必须匹配数字的指定顺序（但算子和括号是免费的）。对于这些变体中的每一个，以及$ \ {+， - ， - \ times，÷\} $的许多子集，我们证明了问题np complete，有时从弱的意义上，有时从强大的意义上讲。这些证据中的大多数都使用了“合理函数框架”，该框架证明了这些问题的等效性，即在正整数中具有值的理性函数中的值。
When can $n$ given numbers be combined using arithmetic operators from a given subset of $\{+, -, \times, ÷\}$ 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 $\{+,-,\times,÷\}$, 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.
