Paper by Erik D. Demaine

Reference:

Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang, “Arithmetic Expression Construction”, in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Hong Kong, December 14–18, 2020, 41:1–41:15.

Abstract:

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.

Comments:

This paper is also available from LIPIcs, and from arXiv.

Updates:

Some of these results were independently discovered by Motoharu Saeki and Harumichi Nishimura, and presented at the 13th Research Meeting of Combinatorial Games and Puzzles Project, 2018; see the slides for the talk “Generalization of make10”.

Length:

The paper is 15 pages.

Availability:

The paper is available in PDF (593k).

See information on file formats.

[Google Scholar search]