Document Open Access Logo

Arithmetic Expression Construction

Authors 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, Lillian Zhang

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.12.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Leo Alcock
  • Harvard University, Cambridge, MA, USA
Sualeh Asif
  • MIT, Cambridge, MA, USA
Jeffrey Bosboom
  • CSAIL, MIT, Cambridge, MA, USA
Josh Brunner
  • CSAIL, MIT, Cambridge, MA, USA
Charlotte Chen
  • MIT, Cambridge, MA, USA
Erik D. Demaine
  • CSAIL, MIT, Cambridge, MA, USA
Rogers Epstein
  • CSAIL, MIT, Cambridge, MA, USA
Adam Hesterberg
  • Harvard University, Cambridge, MA, USA
Lior Hirschfeld
  • MIT, Cambridge, MA, USA
William Hu
  • MIT, Cambridge, MA, USA
Jayson Lynch
  • MIT, CSAIL, Cambridge, MA, USA
Sarah Scheffler
  • Boston University, Boston, MA, USA
Lillian Zhang
  • MIT, Cambridge, MA, USA

Acknowledgements

This work was initiated during open problem solving in the MIT class on Algorithmic Lower Bounds: Fun with Hardness Proofs (6.892) taught by Erik Demaine in Spring 2019. We thank the other participants of that class - in particular, Josh Gruenstein, Mirai Ikebuchi, and Vilhelm Andersen Woltz - for related discussions and providing an inspiring atmosphere.

Cite AsGet BibTex

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 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.12

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Hardness
  • algebraic complexity
  • expression trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Divesh Aggarwal and Ueli Maurer. Breaking RSA generically is equivalent to factoring. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, pages 36-53, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 2009. Google Scholar
  3. David Buchfuhrer and Christopher Umans. The complexity of boolean formula minimization. In Luca Aceto, Ivan Damgard, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, pages 24-35, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. Google Scholar
  4. E. W. Dijkstra. ALGOL-60 translation. Technical Report MR 34/61, Rekenafdeling, Stichting Mathematisch Centrum, 1961. URL: https://ir.cwi.nl/pub/9251.
  5. Peter Downey, Benton Leong, and Ravi Sethi. Computing sequences with addition chains. SIAM Journal on Computing, 10(3):638-646, 1981. Google Scholar
  6. Michael R. Garey and David S. Johnson. Computers and Intractability. W. H. Freeman and Company, New York, 2002. Google Scholar
  7. Daniel M. Gordon. A survey of fast exponentiation methods. Journal of Algorithms, 27:129-146, 1998. Google Scholar
  8. Edith Hemaspaandra and Henning Schnoor. Minimization for generalized boolean formulas. arXiv:1104.2312, 2011. Google Scholar
  9. Valentine Kabanets and Jin yi Cai. Circuit minimization problem. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 73-79, Portland, OR, 2000. Google Scholar
  10. Ueli Maurer. Abstract models of computation in cryptography. In Nigel P. Smart, editor, Cryptography and Coding, pages 1-12, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  11. C. T. Ng, M. S. Barketau, T. C. E. Cheng, and Mikhail Y. Kovalyov. "Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation. European Journal of Operational Research, 207(2):601-604, 2010. URL: https://doi.org/10.1016/j.ejor.2010.05.034.
  12. Arnold Scholz. Aufgaben und Lösungen 253. Jahresbericht der Deutschen Mathematiker-Vereinigung, 47:41-42, 1937. Google Scholar
  13. Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, Advances in Cryptology - EUROCRYPT '97, pages 256-266, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. Google Scholar
  14. Joachim von zur Gathen. Algebraic complexity theory. In Annual Review of Computer Science, volume 3, pages 317-347. Annual Reviews Inc., 1988. Google Scholar
  15. Wikipedia. 24 game. URL: https://en.wikipedia.org/wiki/24_Game.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact