这个问题纯粹是出于好奇。暑假我休学了,打算实现一个算法来解决这个问题只是为了好玩。这就引出了上面的问题,这个问题有多难?
问题:给定一个正整数列表、一组数学运算符和等号 (=)。您能否使用整数(以相同顺序)和运算符(任意次数)创建有效的数学表达式?
遗嘱示例应阐明任何问题:
给定:{2, 3, 5, 25} , {+, -, *,/} , {=}
输出:是
表达式(我认为只有一个)是(2 + 3)* 5 = 25。你只需要输出是/否。
我认为问题出在 NP 中。我这样说是因为这是一个决策问题(是/否答案),我可以找到一个非确定性多时间算法来决定它。
一个。非确定性地选择一系列运算符放置在整数之间。
b.验证你的答案是一个有效的数学表达式(这可以在常量中完成
时间)。
在这种情况下,最大的问题是:问题出在 P 中吗? (即是否有决定它的确定性多时间算法?)或者问题 NP 是否完整? (即,一个已知的 NP Complete 问题可以减少到这个吗?或者等效地,每个 NP 语言多时间都可以减少到这个问题吗?)或者两者都不是? (即 NP 中的问题但不是 NP Complete 中的问题)
注意:此问题陈述假设 P 不等于 NP。另外,虽然我是 Stack Overflow 的新手,但我对 homework 标签很熟悉。这确实只是好奇,不是作业:)
最佳答案
从 Partition problem 直接减少(NP 完全)- 给定一组 N 个整数 S,“有效数学”问题的输入将是 - S 的元素、N-2 个“+”运算符和一个“=”符号。
关于algorithm - 这个 "Valid mathematical expression"是问题P,还是NP?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/975626/