algorithm - 这个 "Valid mathematical expression"是问题P，还是NP？

Question

这个问题纯粹是出于好奇。暑假我休学了，打算实现一个算法来解决这个问题只是为了好玩。这就引出了上面的问题，这个问题有多难？

问题:给定一个正整数列表、一组数学运算符和等号 (=)。您能否使用整数(以相同顺序)和运算符(任意次数)创建有效的数学表达式？

遗嘱示例应阐明任何问题:

给定:{2, 3, 5, 25} , {+, -, *,/} , {=}
输出:是

表达式(我认为只有一个)是(2 + 3)* 5 = 25。你只需要输出是/否。

我认为问题出在 NP 中。我这样说是因为这是一个决策问题(是/否答案)，我可以找到一个非确定性多时间算法来决定它。

一个。非确定性地选择一系列运算符放置在整数之间。
b.验证你的答案是一个有效的数学表达式(这可以在常量中完成 时间)。

在这种情况下，最大的问题是:问题出在 P 中吗？ (即是否有决定它的确定性多时间算法？)或者问题 NP 是否完整？ (即，一个已知的 NP Complete 问题可以减少到这个吗？或者等效地，每个 NP 语言多时间都可以减少到这个问题吗？)或者两者都不是？ (即 NP 中的问题但不是 NP Complete 中的问题)

注意:此问题陈述假设 P 不等于 NP。另外，虽然我是 Stack Overflow 的新手，但我对 homework 标签很熟悉。这确实只是好奇，不是作业:)

Answer 1

从 Partition problem 直接减少(NP 完全)- 给定一组 N 个整数 S，“有效数学”问题的输入将是 - S 的元素、N-2 个“+”运算符和一个“=”符号。