31

据我了解，所有 NP 完全问题都是 NP 难题，但已知一些 NP 难题不是 NP 完全问题，并且 NP 难题至少与 NP 完全问题一样难。

这是否意味着不是 NP 完全的 NP 难题更难？以及如何更难？

4

6 回答 6

23

要回答这个问题，首先需要了解哪些 NP-hard 问题也是 NP-complete。如果一个 NP-hard 问题属于集合 NP，那么它是 NP-complete。要属于集合 NP，需要有一个问题

(i) 一个决策问题，
(ii) 问题的解决方案的数量应该是有限的，并且每个解决方案都应该是多项式长度，以及
(iii) 给定一个多项式长度的解决方案，我们应该能够说出问题的答案是否问题是/否

现在，很容易看出可能存在许多不属于集合 NP 且更难解决的 NP 难题。作为一个直观的例子，我们需要找到实际时间表的旅行商的优化版本比我们只需要确定长度 <= k 的时间表是否存在的旅行商的决策版本更难。

于 2011-06-18T16:41:47.110 回答
10

图灵机停止问题在图灵机和 NP-hard 上是不可判定的，但不是 NPC。显然它更难;）

于 2011-06-19T05:18:30.263 回答
6

图灵停机问题是不可判定的，属于 NP-Hard 集。对于图灵停止问题，我们没有任何决定器，因为它是一种 RE 语言。所以我们没有任何算法来解决它。因此很明显，无法解决的问题也在 NP-Hard 集中。因此 NP-Hard 集还包含我们没有任何算法要解决的语言或问题。

于 2012-09-10T14:20:32.770 回答
6

NP-hard问题集是NP-complete问题集的超集。有比 NP 更“困难”的复杂性类别，例如PSPACE、EXPTIME或EXPSPACE，所有这些都包含 NP-hard 但不是 NP-complete 问题。

于 2010-10-14T11:06:02.217 回答
2

来自http://en.wikipedia.org/wiki/NP-hard#Examples

还有一些决策问题是 NP 难但不是 NP 完全的，例如停机问题。这就是询问“给定程序及其输入，它会永远运行吗？”的问题。这是一个是/否的问题，所以这是一个决策问题。很容易证明停机问题是 NP-hard 但不是 NP-complete。

于 2010-09-28T05:35:01.557 回答
2
  1. NP-complete 必须是 NP 和 NP-hard。
  2. 和 NP-hard 不是 NP-complete 的不是 NP。
  3. 现在根据NP的定义，有人给出问题的答案实例。并且有验证者来验证。
  4. 这意味着 NP-Hard 没有其中任何一个。因此他们很难解决是真的。
于 2012-12-12T07:16:56.870 回答