NP中某些问题的复杂性？

Question

我想总结一下关于复杂性的一些问题。其中哪一个可以在多时间内解决？

(一)求给定图的极大次完备图=团问题 ( II)在给定值和权重的n对象中选择一些元素，使所选元素的权重之和不大于某一特定界限，且值之和最大。 (三)求图的所有圈 (4)找到一条访问每个顶点一次的路径=确定一个图是Hamiltonian的

我认为IV是NP-完全的哈密顿路径，III是NP-硬的和NP-完全的，II是NP-完全的，I是NP-完全的。因此，这些问题的在多时间中求解。

谁能让我更清楚地了解NP-困难和NP-以一种很好的方式完成这些问题？我说的对吗？

Answer 1

正如您已经注意到的，第(1)、(2)和(4)部分都是著名的NP-硬问题(最大团、背包和哈密顿路径)。但是，这些问题并不存在于NP中，因为NP包含决策问题(对这些问题的回答要么是“是”，要么是“否”)，而这些问题不是决策问题。

第(3)部分是比较细微的。这个问题是一个计数问题，目的是确定存在多少个类型的对象，而不是一个决策问题，所以它不可能存在于NP中。据我所知，目前还不知道这个问题有多难。已知，如果可以在多项式时间内求解，则P= NP (详见此链接 )，并且具体的证明表明它也是NP-硬的。

如果P≠NP，则所有这些问题都不能在多项式时间内求解。如果其中任何一个都可以在多项式时间内求解，那么P= NP。他们都很难对付。

希望这能有所帮助！

Answer 2

因为有人问我关于推荐信的事，所以我把我的评论作为答案：

( II)在给定值和权重的n个对象中选择一些元素，使所选元素的权重之和不大于某一特定界限，且值之和最大。

这是一个多时间的背包问题，如果权值不是输入大小的一部分，即解仅为n的多项式。

它在O(n * W)中运行，其中W是允许的最大重量。当然，如果W与n相关，例如W = 2^n，则这不可能是多项式。

你可以在这里读到：

算法

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm