1. Arithmetic Expression Construction
- Author
-
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, and Zhang, Lillian
- Subjects
Computer Science - Computational Complexity - Abstract
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., Comment: 36 pages, 5 figures. Full version of paper accepted to 31st International Symposium on Algorithms and Computation (ISAAC 2020)
- Published
- 2020