7

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

问题：给你一个正整数列表、一组数学运算符和等号（=）。您可以使用整数（以相同顺序）和运算符（任意次数）创建有效的数学表达式吗？

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

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

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

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

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

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

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

4

7 回答 7

6

分区问题（NP-Complete）的直接简化- 给定一组 N 个整数 S，“有效数学”问题的输入将是 - S 的元素、N-2 个“+”运算符和一个 ' ='符号。

于 2009-06-10T14:41:03.177 回答
2

好的，首先，您指定整数的“集合”，但集合根据定义是无序的，因此您的意思是整数的“列表”。

另外，我将在这里做一个可能是错误的假设，即 = 符号总是在列表中倒数第二个和最后一个整数之间出现一次。如果你在中间允许等号，它会变得更加复杂。

这是“有效数学表达式”（VME）是NP完全的实际证明。我们可以从Subset sum做一个归约。请注意，维基百科对子集总和的定义要求子集非空。事实上，如果期望的和也是输入的一部分，那么允许空子集的子集和的更一般问题是 NP 完全的。除非有要求，否则我不会提供证明。给定子集 sum 的实例{i_1, i_2, ..., i_n}以及所需的 sum 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 相乘的数字（包括作为链乘法的一部分）和不与 0 相乘的数字。任何乘以零的数字都不包含在最终总和中。任何未与零相乘的数字都必须添加到最终总和中。

所以我们已经证明了这个 VME 的实例是可解的，如果且仅当子集和的对应实例是可解的，所以归约是完整的。

编辑：分区减少（带有注释）也有效，并且更好，因为它允许您将等号放在任何地方。整洁的！

于 2009-06-10T15:49:25.723 回答
2

关于如何检查 NP 完整性似乎存在某种混淆。在特定意义上，NP 完全问题至少与 NP 中的任何其他问题一样难。假设我们正在与 3SAT 进行比较，正如一些海报正在尝试做的那样。

现在，将给定的问题简化为 3SAT 并不能证明任何事情。那么确实，如果 3SAT 可以有效地解决（意味着 P=NP），那么给定的问题就可以有效地解决。但是，如果给定的问题可以有效地解决，那么它可能只对应于 3SAT 的简单特殊情况。

我们必须将 3SAT 减少到给定的问题。这意味着我们必须制定一个规则来将任意 3SAT 问题转换为给定问题的示例，这样给定问题的解决方案就会告诉我们如何解决 3SAT 问题。这意味着 3SAT 不会比给定的问题更难。由于 3SAT 是最难的，那么给定的问题也必须是最难的。

分区问题的减少是有效的。这个问题是这样工作的：给定一个整数的多重集 S，我们是否可以将它分成两个不相交的子集，它们之间包括 S 的每个成员，使得不相交子集的总和相等？

为此，我们构造一个从 0 开始的序列，包含 S 的每个元素，然后是 0。我们使用 {+, -} 作为操作集。这意味着 S 的每个元素将被添加或减去总计为 0，这意味着添加的元素的总和与减去的元素的总和相同。

因此，这个问题至少和分区问题一样难，因为如果我们能解决给定的分区程序，我们就可以解决一个示例分区程序，因此是 NP 完全的。

于 2009-06-10T16:25:13.843 回答
1

现在没有时间给出完整的答案，但您可以描述从这个问题到背包问题的简化。

使用动态规划可以实现伪多项式时间解。请注意，这与问题确实是 NP 完全这一事实并不冲突。

于 2009-06-10T13:58:41.127 回答
1

NP完全需要满足两个属性。

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

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

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

因此它是NP完全的。

（编辑）回答以下评论：

我将证明 SAT 可还原为当前问题，并且由于 3SAT 可还原为 SAT，因此结果如下。

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

(x 1 V x 2 V x 3 V ... x n V y 1 )

(x 1 V x 2 V x 3 V ... x n V y 2 )

(x 1 V x 2 V x 3 V ... x n V y 3 )

.

.

.

（x 1 V x 2 V x 3 V ... x n V y 64）

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

如果没有一个表达式为真，那么完整的表达式将评估为 FALSE，除非我们替换所有可能的值，否则无法检查，即 x 1到 x n作为 n 个数字，y 1到 y 64作为可以应用运算符的各种方式（这需要注意顺序）

这种转换是在 POLY 时间内进行的，并且如果数学表达式有效，则给定的布尔公式是可满足的，等等。

有人注意到一个缺陷吗？

于 2009-06-10T14:45:32.450 回答
0

这并不是对您的复杂性问题的真正答案，但您的问题听起来有点像倒计时问题。快速搜索出现了这篇论文：http ://www.cs.nott.ac.uk/~gmh/countdown.pdf

于 2009-06-10T13:49:52.203 回答
0

我现在不需要时间来做一个证明，但预感告诉我它可能不在 P 中。你可以为算术定义一个语法，然后这个问题相当于寻找是否有一个有效的解析树使用所有这些终端。我相信这个问题在 NP 中，但在 P 之外。

于 2009-06-10T15:50:57.810 回答