trh*_*178 7 algorithm math np-complete
这个问题纯粹是出于好奇.我今年夏天不在学校,并且正在实施一种算法来解决这个问题,这只是为了好玩.这导致了上述问题,这个问题有多难？
问题是:给出一个正整数列表,一组数学运算符和等号(=).你能用整数(按照相同的顺序)和运算符(任意次数)创建一个有效的数学表达式吗？
一个例子应该澄清任何问题:
给定:{2,3,5,25},{+, - ,*,/},{=}
输出:是
表达式(我认为只有一个)是(2 + 3)*5 = 25.你只需要输出YES/NO.
我相信问题出在NP.我这样说是因为这是一个决策问题(是/否答案),我可以找到一个决定它的非确定性多时间算法.
一个.非确定性地选择要在整数之间放置的运算符序列.
湾 验证你的回答是一个有效的数学表达式(这可以在恒定的时间内完成).
在这种情况下,最大的问题是:P中的问题是什么？(即是否有一个确定性的多时间算法决定它？)或问题NP是否完整？(即,一个已知的NP完全问题可以减少到这个吗？或者相当于每个NP语言的多边形时间是否可以减少到这个问题？)或者两者都没有？(即NP中的问题但不是NP完成)
注意:此问题陈述假设P不等于NP.此外,虽然我是Stack Overflow的新手,但我对家庭作业标签很熟悉.这确实只是好奇心,而不是作业:)