logo标签列表

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

algorithmmathnp-complete
7

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

问题：给定一组正整数、一组数学运算符和等号(=)，你能否使用这些整数(按照相同顺序)和运算符(任意次数)创建一个有效的数学表达式？

下面的例子将澄清任何问题：

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

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

我认为这个问题属于NP问题。我这样说是因为它是一个决策问题(是/否答案)，而且我可以找到一个非确定性多项式时间算法来判断它。

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

在这种情况下，大问题是：这个问题是否属于P类问题？(即是否存在一个确定性多项式时间算法来判断它？)或者这个问题是NP完全问题吗？(即是否可以将已知的NP完全问题归约到这个问题上？或等价地，是否每个NP语言都可以在多项式时间内归约到这个问题上？)或者两者都不是？(即问题属于NP但不是NP完全问题)

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

P != NP是一个被广泛接受的猜想。它尚未被证明或证伪。在提出问题时，我总是被告知要尽可能精确。这就是为什么我认为有必要将其作为注释包含进来的原因。 - trh178
@Toddeman - 好的理性评论，聪明的屁话已被删除！ - Gavin Miller
你的表达式意味着许多其他有效的表达式：2+3 = 25/5，25/5 - 3 = 2等等。当然，这与问题实际上没有任何关系。 - SingleNegationElimination
@TokenMacGuy - 问题说明整数必须按照给定的顺序排列。 - Shane Fulmer
由于整数必须保持有序，将其称为集合只会让事情更加混乱。集合没有顺序。 - David Thornley
@David Thornley - 很好的观点。已编辑以修复。 - trh178
7个回答
6
一个简单的约化来自划分问题（这是NP-完全问题） - 给定一个由N个整数组成的集合S，输入到“有效数学”问题将是 - S的元素，N-2个'+'运算符和一个'='号。
3
您不能指定运算符的数量。但是，您可以以0开始和结束整数序列，并允许使用加号和减号。这是一种有效的约简。 - David Thornley
+1 对David Thornley的评论表示赞同，这使它成为正确答案 :) - ShreevatsaR
2
好的，首先，您指定了“整数集”，但是按照定义，集合是无序的，所以您的意思是“整数列表”。
此外，我要做一个可能是错误的假设，即等号始终恰好出现一次，在您的列表中倒数第二个和最后一个整数之间。如果您允许在中间使用等号，则变得更加复杂。
下面是一个实际的证明，证明“有效的数学表达式”（VME）是NP完全的。我们可以从子集和问题进行归约。请注意，维基百科对子集和问题的定义要求子集非空。事实上，如果所需总和也是输入的一部分，则允许空子集的子集和问题更为一般化，也是NP完全的。除非有要求，否则我不会给出那个证明。给定子集和实例{i_1, i_2, ..., i_n}以及所需总和s，创建以下VME实例：
{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

如果子集和问题的实例有解，则存在一些整数的子集加起来等于0。如果整数 i1 是求和的一部分，则将其与其对应的零（紧挨着左边的零）相加；如果 i1 不是求和的一部分，则将其乘以-1。在每个零和右侧项之间插入一个加号。
以维基百科的例子为例：
{−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实例是可解的，因此缩减是完整的。
编辑：Partition缩减（带注释）也有效，并且更好，因为它允许您在任何地方放置等号。很棒！
2
似乎有些混淆如何检查NP完备性。 NP完全问题在某种特定意义上至少与NP中的任何其他问题一样困难。 假设我们正在与3SAT进行比较，就像一些海报上所尝试的那样。
现在，将给定问题简化为3SAT并不能证明什么。 然后，如果可以有效地解决3SAT（意味着P = NP），则可以有效地解决给定问题。 但是，如果可以有效地解决给定问题，则可能仅对应于3SAT的易于特殊情况。
我们必须将3SAT简化为给定问题。 这意味着我们必须制定一条规则，将任意3SAT问题转换为给定问题的示例，以便给定问题的解决方案将告诉我们如何解决3SAT问题。 这意味着3SAT不能比给定问题更难。 由于3SAT是可能的最难问题，因此给定问题也必须是可能的最难问题。
来自Partition问题的简化起作用。 该问题的工作方式如下：给定整数的多重集合S，我们可以将其分成两个不相交的子集，使它们之间包括S的每个成员，并且两个不相交子集的总和相等吗？
为此，我们构造一个从0开始的序列，包含S的每个元素，然后是0。 我们使用{+，-}作为操作集。 这意味着S的每个元素将被添加或减去以总和为0，这意味着添加元素的总和与减去元素的总和相同。
因此，该问题至少与Partition问题一样困难，因为如果我们可以解决给定的问题，则可以解决一个示例Partition程序，因此是NP完全的。
1

现在没有时间给出完整的答案，但是你可以将这个问题描述为背包问题的简化版。

使用动态规划，你可以实现伪多项式时间复杂度的解决方案。请注意，这并不与该问题确实是NP完全问题相矛盾。

-1 是用于多项式时间解决方案的，但考虑到背包问题是 NP 问题，这是不正确的。 - Gavin Miller
然而，您现在已经提到了伪多项式时间，所以我撤回了我的反对票。 - Gavin Miller
背包问题有一种伪多项式时间解决方案，尽管它实际上是NP完全问题。这是由于问题输入定义的方式。请参见维基百科链接。 - Yuval Adam
2
“你可以描述一个从这个问题到背包问题的约化” - 这并没有帮助。为了证明这个问题是NP完全问题，你需要将一个NP完全问题从中约化出来。 - ShreevatsaR
1

要满足NP完全的两个条件。

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

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

我们已经证明了1。2的结果是因为NP中的每个问题都可以在多项式时间内归约为3SAT，而3SAT可以归约为当前问题。

因此它是NP完全的。

（编辑）回答下面的评论：

我将证明SAT可以归约为当前问题，由于3SAT可以归约为SAT，因此结果成立。

输入公式是以下表达式的连接：

(x1 V x2 V x3 V ... xn V y1)

(x1 V x2 V x3 V ... xn V y2)

(x1 V x2 V x3 V ... xn V y3)

.

.

.

(x1 V x2 V x3 V ... xn V y64)

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

如果没有一个表达式为真，则完整表达式将计算为FALSE，除非我们将所有可能的值替换，即将x1到xn作为n个数字，将y1到y64作为可以应用运算符的各种方式（这解决了顺序问题）

此转换在POLY时间内完成，给定的布尔公式是可满足的，当且仅当数学表达式是有效的等等。

有人注意到一个缺陷吗？

1
你能展示一下3SAT如何归约到这个问题吗？我真的想不出来怎么做。你会如何将一个3SAT问题建模成整数序列和一组操作呢？ - David Thornley
0
0

我现在没有时间来证明，但直觉告诉我这个问题可能不属于P类。你可以为算术定义一个语法，那么这个问题就等同于找出是否存在一个有效的解析树，使用了所有这些终端符号。我认为这个问题属于NP，但不属于P。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接