这个问题纯属出于好奇。我暑假不上学,想实现一个算法来解决这个问题,只是为了好玩。这就引出了上面的问题,这个问题有多难?
问题:给定一组正整数、一组数学运算符和等号(=),你能否使用这些整数(按照相同顺序)和运算符(任意次数)创建一个有效的数学表达式?
下面的例子将澄清任何问题:
给定:{2, 3, 5, 25},{+,-,*,/},{=}
输出:是
表达式(我认为只有一个)是(2 + 3) * 5 = 25。你只需要输出是/否。
我认为这个问题属于NP问题。我这样说是因为它是一个决策问题(是/否答案),而且我可以找到一个非确定性多项式时间算法来判断它。
a. 非确定性地选择要放置在整数之间的运算符序列。
b. 验证你的答案是一个有效的数学表达式(这可以在常量时间内完成)。
在这种情况下,大问题是:这个问题是否属于P类问题?(即是否存在一个确定性多项式时间算法来判断它?)或者这个问题是NP完全问题吗?(即是否可以将已知的NP完全问题归约到这个问题上?或等价地,是否每个NP语言都可以在多项式时间内归约到这个问题上?)或者两者都不是?(即问题属于NP但不是NP完全问题)
注意:这个问题陈述假设P不等于NP。另外,虽然我是Stack Overflow的新手,但我熟悉作业标签。这确实只是好奇,而不是作业 :)