logo标签列表

不是NP完全问题的NP难问题更难吗？

computer-sciencecomplexity-theoryp-np
31

据我所知，所有NP完全问题都是NP难问题，但其中一些NP难问题已被证明不是NP完全问题，而NP难问题至少与NP完全问题同等难度。

这是否意味着那些不是NP完全问题的NP难问题更难？它们为什么更难？

可能是NP vs NP-Complete vs NP-Hard的重复问题。 - Jouni K. Seppänen
6个回答
23
要回答这个问题，你首先需要了解哪些NP难度问题也是NP完全问题。如果一个NP难度问题属于NP集合，则它是NP完全问题。要属于NP集合，一个问题需要满足以下条件：
(i) 是决策问题，
(ii) 问题的解的数量应该是有限的，并且每个解的长度都应该是多项式级别的，
(iii) 给出一个多项式级别的解，我们应该能够判断问题的答案是“是”或“否”。
现在，很容易看出可能会有许多NP难度问题不属于NP集合，并且更难解决。作为一个直观的例子，需要找到一个实际的时间表的旅行推销员问题的优化版本比确定长度小于等于k的时间表是否存在的决策版本更难。
10

图灵机停机问题在图灵机上是不可判定的，而且是NP难的，但不是NPC。显然它更难 ;)

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

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

2

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

还有一些决策问题是NP-hard但不是NP-complete，例如停机问题。这个问题是问“给定一个程序和它的输入，它会永远运行吗？” 这是一个是/否问题，因此这是一个决策问题。很容易证明停机问题是NP-hard但不是NP-complete。

2
  1. NP完全问题必须是NP问题和NP难问题。
  2. 而不是NP完全的NP难问题不是NP问题。
  3. 现在根据NP的定义，有人给出问题实例的答案，还有验证者来验证。
  4. 这意味着NP难问题没有其中之一。因此，它们很难解决是正确的。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接