这是“有效数学表达式”问题 P 还是 NP？

Question

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

问题：您将获得一个正整数列表、一组数学运算符和等号 (=)。您能使用整数（按相同顺序）和运算符（任意次数）创建有效的数学表达式吗？

一个例子应该可以澄清任何问题：

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

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

我相信问题出在NP上。我这样说是因为这是一个决策问题（是/否答案），并且我可以找到一个非确定性多时间算法来决定它。

A。不确定地选择一系列运算符放置在整数之间。
b.验证您的答案是有效的数学表达式（这可以在恒定时间内完成）。

在这种情况下，最大的问题是：问题出在P上吗？（IE。是否有一个确定性的多时间算法来决定它？）或者问题是否 NP 完整？（IE。一个已知的 NP 完全问题可以简化为这样吗？或者等价的是，每个 NP 语言多时间都可以简化为这个问题吗？）或者两者都不是？（IE。NP 问题但非 NP 完全问题）

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

Answer 1

从分区问题（这是NP完全） - 给定一个N个整数S的集合，输入到“有效数学”的问题将是 - S，N-2“+”操作符的元件和一个“=”标志。

Answer 2

有似乎是某种混乱的有关如何检查NP-完整性。一个NP完全问题是至少如硬，在一个特定的意义上，如在NP任何其他问题。假设我们比较3SAT，一些海报正在尝试做的。

现在，降低了给定的问题，以3SAT证明什么。这是真实的，然后，如果3SAT可以有效地解决（意味着P = NP），则给定的问题可以有效地解决了。然而，如果给定的问题可以有效地解决了，那么也许仅对应于3SAT的容易特殊情况。

我们将不得不减少3SAT给定的问题。这意味着我们将不得不作出了一个规则来变换任意3SAT问题给定问题的例子，比如给定问题的解决会告诉我们如何解决这个问题3SAT。这意味着，3SAT不能超过给定的问题更难。由于3SAT是最难的可能，则给定的问题也必须是最难的可能。

从分区问题的减小起作用。这个问题是这样工作的：给定整数的多集S，我们可以划分为两个不相交的子集这使得它们之间包括S的每个部件，以使得所述不相交的子集的和相等

要做到这一点，我们构建以0开头的序列，含S的每个元素，然后0。我们使用{+， - }作为操作集。这意味着S的每个元素将被相加或相减，至总量为0，这意味着添加元素的总和是一样的减去元素的总和。

因此，该问题是至少硬如分区问题，因为我们可以解决一个示例分区程序，如果我们能够解决给定的一个，并且因此是NP完全问题。

Answer 3

OK，首先，你指定的整数“设置”，而是一组被定义无序的，所以你的意思是一个整数的“名单”。

另外，我要在这里做一个假设，这可能是错误的，这是一个等号（=）总是出现正好一次，倒数第二和清单上的最后一个整数之间。如果允许等于在中间的签署，它变得更加复杂了。

下面是一个实际的证明“有效数学表达式”（VME）是NP完全。我们可以做从子集和减少。需要注意的是维基百科的子集和的定义需要子集非空。事实上，这是事实，子集和允许空子集的更普遍的问题是NP完全，如果所需的总和也是输入的一部分。我不会放弃举证，除非请求。给定子集总和{i_1, i_2, ..., i_n}的实例与期望的总和s沿，创建VME的以下实例：

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

如果子集之和的实例是可解的，则存在的整数的一些子集，增加了为0。如果整数i1是总和的一部分，与其相应的零（立即向左）添加它，如果i1不和的部分，乘以。每个零并且术语向右之间，插入一个附加标志。

以维基百科示例

{−7, −3, −2, 5, 8}

其中{ −3, −2, 5}总和为0，我们将编码它作为

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

和将所得的表达将是

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

现在，我们还需要证明任何解决VME的这种情况下导致解决子集和实例。这比你想象的更容易。当我们观察一个产生的表达，我们可以基团的数字到的那些乘以0（包括作为链乘法的一部分）和那些没有。这被乘以零的任何数不包含在最终的总和。不与一个零乘以任意数量的必须添加到最终的总和。

因此，我们已经表明，VME的这个实例是可解当且仅当子集和对应的实例是可解的，所以还原完成。

编辑：分区减少（与评论）的作品，以及，是更好，因为它可以让你把任何地方等号签署。整齐！

Answer 4

对于不具备完整的答案时的权利，但你可以从这个问题描述降低到的背包问题。

使用动态编程可以实现的伪多项式时间的解决方案。需要注意的是这个的不冲突的的事实，这个问题确实是NP完成。

Answer 5

要使其成为 NP 完全的，需要满足两个属性。

决策问题 C 是 NP 完全的，如果：

1. C 属于 NP，并且
2. NP 中的每个问题都可以在多项式时间内简化为 C。

我们已经建立了1.2 是因为 NP 中的每个问题都可以简化为 3SAT，并且 3SAT 可以简化为当前问题。

因此它是NP完全的。

（编辑）回答以下评论：

我将证明 SAT 可简化为当前问题，并且由于 3SAT 可简化为 SAT，结果如下。

输入公式是以下表达式的合取：

（X₁ 电压x₂ 电压x₃ 维...X_n 维₁)

（X₁ 电压x₂ 电压x₃ 维...X_n 维₂)

（X₁ 电压x₂ 电压x₃ 维...X_n 维₃)

.

.

.

（X₁ 电压x₂ 电压x₃ 维...X_n 维₆₄)

其中每个 y_我 是一个布尔值，基于所有 x 之间应用的运算符的顺序_我是。即，y_我 总共可以取 4x4x4x4x1 个值（假设只有 +、-、x、/ 是运算符，= 始终是最后一个运算符；如果修改操作符集以包含其他操作符，则可以更改此值）

如果没有一个表达式为 true，那么完整的表达式将计算为 FALSE，并且无法进行检查，除非我们替换所有可能的值，即 x₁ 通过 x_n 作为 n 个数字和 y₁ 通过 y₆₄ 作为应用运算符的各种方式（这需要注意顺序）

这种转换是 POLY 时间的，并且给定的布尔公式是可满足的，当且仅当数学表达式有效，等等。

有人注意到一个缺陷吗？

Answer 6

这是不是一个真正的答案，你的复杂的问题，但你的问题听起来有点像的倒计时的问题。快速搜索止跌回升本文： HTTP：//www.cs.nott .ac.uk /〜GMH / countdown.pdf

Answer 7

我没有时间来解决目前的证明，但直觉告诉我，这可能不是P.您可以定义算术语法，然后这个问题相当于找到，如果有一个使用所有这些终端有效的解析树。我相信即这个问题是在NP但外面的P