Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.4230/LIPIcs.ISAAC.2020.12 | ISAAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 13 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leo Alcock | 1 | 0 | 0.34 |
| Sualeh Asif | 2 | 0 | 0.68 |
| Jeffrey Bosboom | 3 | 117 | 7.70 |
| Josh Brunner | 4 | 0 | 1.01 |
| Charlotte Chen | 5 | 0 | 0.34 |
| Erik D. Demaine | 6 | 4624 | 388.59 |
| Rogers Epstein | 7 | 0 | 0.34 |
| Adam Hesterberg | 8 | 4 | 7.07 |
| Lior Hirschfeld | 9 | 0 | 0.34 |
| William Hu | 10 | 0 | 1.01 |
| Jayson Lynch | 11 | 0 | 2.70 |
| Sarah Scheffler | 12 | 0 | 1.01 |
| Lillian Zhang | 13 | 0 | 0.34 |