NP/NP-Complete/NP-HARD与时间复杂性之间的关系是什么？

Question

我熟悉每个类别的一些问题，即使定义基于集合和多项式可降低性，我也看到了具有时间复杂性的模式。 NP问题似乎为$ O（2^n）$（当然减去P问题），而NP-HARD问题似乎更糟：$ n^n $或$ n！$（国际象棋，TSP）。这是一种误导性的解释吗？

Answer 1

参见的定义 NP完整性. 。为了解决NP的问题，

1. 需要在NP和
2. 所有NP问题都需要在多项式时间内还原。

仅条件2就意味着NP硬。因此，NP完全问题是NP问题和NP硬问题的交集。

np $ subseteq $ exptime，因此对于某些多项式$ p（n）$，可以以$ 2^{o（p（n））} $解决NP问题。但是众所周知，如果p $ = $ np，则可以在多项式时间内解决NP问题。

NP硬问题至少与NP问题一样困难 - 您引用了一些例子。

Answer 2

您的理解在很高的水平上是正确的。 NP中存在的一个问题意味着问题是“容易”（从某种意义上说），而问题是NP-HARD意味着问题是“困难”（从另一个特定意义上），我认为您理解这一点正确。

但是，您的理解是通过多种方式误导的。

首先，在NP中存在一个问题，而NP-HARD的问题并非互斥。正如戴夫·克拉克（Dave Clarke）所解释的那样，当NP和NP-Hard中的问题都出现在NP和NP-HARD中时，我们说问题是NP的完整性。

其次，尚不清楚（或认为）NP中的所有问题都可以在时间上确定性解决（2ⁿ），或时间2^o（o）n) 对于这个问题。众所周知，NP中的所有问题都可以在时间2中确定性解决^poly（n) (= 2^no（1））。时间2^poly（n) 在复杂性理论中通常称为“指数时间”，但请注意，相同的术语“指数时间”有时也可以参考时间2^o（o）n).

顺便说一句，虽然您是正确的，因为旅行销售人员问题（TSP）是NP-HARD，但您似乎在暗示TSP不在NP中。这一点值得关注。

定义为搜索问题的TSP（“给定加权有向图，找到最小总重量的哈密顿电路”）确实不能在NP中，因为根据定义，NP是一类决策问题。但是，TSP的自然决策版本（“给定加权有向图和阈值 k, ，确定给定的图是否具有最多总重量的哈密顿电路 k”）在NP中，该决策版本有时也称为旅行销售人员问题。这种调用搜索版本和以同名决策版本的做法通常很方便，但是由于这种情况，发生了一件奇怪的事情 - 有些人说“ TSP是NP-Complete”，而其他人则说“ TSP不在NP中。 ，”两者都是正确的。看 我的帖子 在Math.stackexchange.com上，有关此公约的更多信息。

Answer 3

您的运行时间摘要有很多例外。

可能最值得注意的是，可以通过动态编程以$ n^22^n $时间解决TSP（ HOWH-KARP算法）;您不需要全部$ n！$。

有一些NP硬性问题甚至可以比$ 2^n $更快解决。子集总和可以在$ o（2^{n/2}）$ time中求解，或大约$ o（1.4^n）$。还有许多其他NP硬性问题可以在$ c^n $时间内使用$ c <2 $解决。

一些NP硬性问题，例如分区，只是“弱的np- hard”，并且具有伪型解决方案。这意味着在输入的值中有多项式的运行时间（因此，如果集合中的最大项目具有尺寸$ M $，则运行时间与$ M $以及集合$ n $的大小成正比）。同等地，如果输入为一单元提供，则可以在多项式时间内解决这些问题。大多数类似于分区的问题（例如背包）属于这一类别，以及很多 - 但并非全部 - NP硬度调度问题。根据问题实例，这可能大于$ 2^n $，甚至是多项式。

图同构为NP，但可能不是NP-HARD，并且可以在$ O（2^{ sqrt {n log n}}）中求解$ time（不是很好，但比$ 2^n $更好）。可以更快地解决NP中的一些问题，但不知道NP-HARD。例如，可以在$ e^{（64n/9）^{1/3}（ log n）^{2/3}} $时使用N-二元数字的时间来解决。 一般数字字段筛。

与其他因素相比，还有其他几个因素可能会使NP硬化问题或多或少地被认为是困难的，例如，在多项式时间内它们可以近似地近似。