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的完整性。 当给出一套操作、输入和目标值时, 是否有一棵表达式树, 这些输入和操作对目标进行评估? 我们考虑树结构的变异性, 以及表达式中不允许括号的变异性 。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
【硬核书】矩阵代数基础,248页pdf
专知会员服务
83+阅读 · 2021年12月9日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
专知会员服务
60+阅读 · 2020年3月19日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
150+阅读 · 2019年10月12日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
【ACL2020放榜!】事件抽取、关系抽取、NER、Few-Shot 相关论文整理
深度学习自然语言处理
18+阅读 · 2020年5月22日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
关关的刷题日记90 – Leetcode 400. Nth Digit
专知
3+阅读 · 2018年1月8日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年12月25日
Arxiv
8+阅读 · 2021年1月28日
Arxiv
5+阅读 · 2017年11月30日
VIP会员
相关主题
相关资讯
【ACL2020放榜!】事件抽取、关系抽取、NER、Few-Shot 相关论文整理
深度学习自然语言处理
18+阅读 · 2020年5月22日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
关关的刷题日记90 – Leetcode 400. Nth Digit
专知
3+阅读 · 2018年1月8日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员