3

对于一个 NP 完全问题，它必须属于 NP 类，并且必须有一个多项式时间算法将其简化为一个 NP 完全问题。

现在，如果我们只有一个指数时间算法来减少。这个问题还会被称为 NP-complete 吗？还是不存在这样的问题？

编辑：另外请告诉我是否存在任何此类问题，如果存在，那么它属于哪个类？

4

4 回答 4

4

只有当其他 NP 问题可以在多项式时间内归约到它时，它才能被认为是 NP 完全的。这是一个有用的定义的原因是，如果我们找到一个多项式时间算法，它会自动为所有 NP 问题给出一个。如果我们允许指数时间减少，但找到了减少问题的多项式时间解决方案，那实际上并不能帮助我们解决我们将其减少到的问题。

希望这可以帮助。

于 2013-02-09T15:58:52.340 回答
1 
Are such problems NP-complete?

没有。证明：

让你的问题 = A。

让 NP 完全问题在（至少）指数时间 = B 中减少。“至少”因为您可以做额外的琐碎工作来达到指数时间，或者遵循不太理想的方法（证明有不存在更有效的减少策略可能非常困难，可能与 N != NP 在同一个球场，迄今为止，尚未解决）。

由于 B 是 NP 完全的，“NP 中的每个问题都可以在多项式时间内简化为 B”。

如果 A 在 NP 中，那么它必须是多项式时间可约化为 B。但它不是，所以它不在 NP 中。

因此它不能是NP完全的。

更简单地说 - NP 中的任何问题最多需要和 A 一样难，而且显然不是。

Are there such problems?

我在想这可能是个问题：（递归背包）（我不介意评论是否是聪明人做的）

给定一组项目，每个项目都有一个权重和一个值，找到一个具有最大总权重 A 的子集，并在该子集中找到具有某个最大总权重 C 的子集，目标是最大化两者的值之和子集。

To which class does it belong?

我很确定这些没有专门的名称，但我认为其中很多（或全部？）都是NP-hard。证明：（至少对于上面的问题，假设是这样的问题）

定义：“如果...（一个 NP 完全问题）L 可以通过具有 H 的预言机的预言机在多项式时间内解决，则问题 H 是 NP-hard”。

让我们假设上面的例子就是这样一个问题，让它 = H。所以假设我们有一个可以在恒定时间内解决上述问题的预言机。但是背包问题只是上述（C = 0）的一个特例，因此我们可以使用预言机在常数时间（即多项式时间）内解决背包问题。

不确定是否可以通用地证明它。但是任何给定的问题都可以通过将给定问题简化为上述问题或通过将给定问题简化为背包问题来解决。

编辑：哦，看起来他们可能确实有一个名字，2-EXPTIME。

于 2013-02-09T19:11:18.033 回答
0

复杂性理论中的完整性总是针对特定类型的归约来定义的，有时从上下文中知道，因此没有明确提及。著名的 NP 完全问题类被定义为多项式时间减少的完全问题，原因在 Richard Rast 的回答中给出。

您可以为 EXPTIME 减少定义一类 NP 完全问题，但这个类不是很有趣。如果减少是允许指数时间的，那么它可以完全解决原始问题并产生目标问题的平凡实例。这意味着 NP 中的每个问题都可以通过这种类型的归约归约为所有其他问题，因此 NP 中的每个问题都是 NP 完全的，以减少指数时间。

简短版本：只有当它们（至少被认为是）弱于被归约的问题类别时，归约才有意义。

于 2013-02-09T20:54:12.027 回答
0

如前所述，您的问题的方向是错误的。如果 NP 中的每个问题 B 都可以在多项式时间内归约到问题 A，则问题 A 是 NP 完全的。所以我假设您的问题是，这种归约是否必须在多项式时间而不是指数时间内。

如果您允许指数时间减少：采取以下决策问题 X：“输入是否为 YES？” 这几乎是最简单的决策问题。如果输入是YES，答案是YES，如果输入不是YES，答案是NO。但是 NP 中的每个问题都可以在指数时间内简化为问题 X。当然，我们不想将问题 X 称为“NP 完全”。因此，不允许指数时间减少，因为允许它会使术语“NP-complete”完全没有意义。

于 2014-03-22T23:29:12.670 回答