We show NP-completeness for various problems about the existence of arithmetic expression trees. When given a set of operations, inputs, and a target value does there exist an expression tree with those inputs and operations that evaluates to the target? We consider the variations where the structure of the tree is also given and the variation where no parentheses are allowed in the expression.
翻译:我们对关于算术表达式树存在的各种问题表现出NP的完整性。 当给出一套操作、输入和目标值时, 是否有一棵表达式树, 这些输入和操作对目标进行评估? 我们考虑树结构的变异性, 以及表达式中不允许括号的变异性 。