Arithmetic Expression Construction

11/23/2020
by   Leo Alcock, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset