The Computational Complexity of Finding Arithmetic Expressions With and\n Without Parentheses

2021/10/26 by Jayson Lynch, Lynch, Jayson, Yan +1
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques

paper · pdf · doi:10.48550/arxiv.2110.14045

openalex publication_date 2021/10/26 · openalex created_date 2022/07/23 · openalex updated_date 2026/07/28

Abstract

We show NP-completeness for various problems about the existence of\narithmetic expression trees. When given a set of operations, inputs, and a\ntarget value does there exist an expression tree with those inputs and\noperations that evaluates to the target? We consider the variations where the\nstructure of the tree is also given and the variation where no parentheses are\nallowed in the expression.\n

Citations

• Computing Sequences with Addition Chains
• Measuring Mathematical Problem Solving With the MATH Dataset
• Solving Machine Learning Problems

Related

• Counting the number of inequivalent arithmetic expressions on n variables
• Arithmetic Expression Construction
• Solving General Arithmetic Word Problems
• Regular expression length via arithmetic formula complexity
• Arithmetic, Infinite Trees, and Second-order Subsystems: Notes and Observations