Arithmetic expression construction
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...
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143959 |
| _version_ | 1811095946933567488 |
|---|---|
| author | Alcock, L Bosboom, J Chen, C Epstein, R Hirschfeld, L Lynch, J Zhang, L Asif, S Brunner, J Demaine, ED Hesterberg, A Hu, W Scheffler, S |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Alcock, L Bosboom, J Chen, C Epstein, R Hirschfeld, L Lynch, J Zhang, L Asif, S Brunner, J Demaine, ED Hesterberg, A Hu, W Scheffler, S |
| author_sort | Alcock, L |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:35:22Z |
| format | Article |
| id | mit-1721.1/143959 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:35:22Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1439592023-01-20T16:28:13Z Arithmetic expression construction Alcock, L Bosboom, J Chen, C Epstein, R Hirschfeld, L Lynch, J Zhang, L Asif, S Brunner, J Demaine, ED Hesterberg, A Hu, W Scheffler, S Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. 2022-07-22T14:19:40Z 2022-07-22T14:19:40Z 2020-12-01 2022-07-22T14:16:37Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143959 Alcock, L, Bosboom, J, Chen, C, Epstein, R, Hirschfeld, L et al. 2020. "Arithmetic expression construction." Leibniz International Proceedings in Informatics, LIPIcs, 181. en 10.4230/LIPIcs.ISAAC.2020.12 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 3.0 unported license https://creativecommons.org/licenses/by/3.0/ application/pdf DROPS |
| spellingShingle | Alcock, L Bosboom, J Chen, C Epstein, R Hirschfeld, L Lynch, J Zhang, L Asif, S Brunner, J Demaine, ED Hesterberg, A Hu, W Scheffler, S Arithmetic expression construction |
| title | Arithmetic expression construction |
| title_full | Arithmetic expression construction |
| title_fullStr | Arithmetic expression construction |
| title_full_unstemmed | Arithmetic expression construction |
| title_short | Arithmetic expression construction |
| title_sort | arithmetic expression construction |
| url | https://hdl.handle.net/1721.1/143959 |
| work_keys_str_mv | AT alcockl arithmeticexpressionconstruction AT bosboomj arithmeticexpressionconstruction AT chenc arithmeticexpressionconstruction AT epsteinr arithmeticexpressionconstruction AT hirschfeldl arithmeticexpressionconstruction AT lynchj arithmeticexpressionconstruction AT zhangl arithmeticexpressionconstruction AT asifs arithmeticexpressionconstruction AT brunnerj arithmeticexpressionconstruction AT demaineed arithmeticexpressionconstruction AT hesterberga arithmeticexpressionconstruction AT huw arithmeticexpressionconstruction AT schefflers arithmeticexpressionconstruction |