When can $n$ given numbers be combined using arithmetic operators from a given subset of $\{+, -, \times, \div\}$ 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,\div\}$, 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.
翻译:何时能使用某子数的计算操作员来将给定数字组合为美元, - -,\ time,\ div\\ $,\ div\ $ 来获得给定目标数字? 我们研究了这个亚氏表达式构造问题的三种变式: 当表达式(1) 不受约束时; (2) 具有一个指定的括号和操作员模式( 仅需要将数字划为空白); 或者 (3) 必须匹配数字的指定顺序( 但操作员和括号是自由的 ) 。 对于其中的每一种变式, 以及其中的许多子集 $, $, -,\ \ time,\ div\ $, 我们证明了NP- 问题的完整性, 有时是软弱的, 有时是强烈的。 这些证明使用了“ 合理功能框架 ”, 这证明合理函数中的值与正整值相等 。