我即将不可判定问题和NP困难问题之间的关系有点混乱。 无论是NP难问题的不可判定问题的一个子集，或者他们只是相同的，平等的，或者是他们没有可比性？
对于我来说，我已经与我的朋友们争辩说，不可判定问题的一个超集的NP难问题。 有将存在一些问题不在NP难，但不可判定的。 但是，我发现这种说法是弱，很困惑了一下。 是否存在一些不可判定的NP完全问题？ 是有在NP硬的任何问题，其是可判定的??。
有些讨论将是极大的帮助！ 谢谢！
Answer 1:
不可判定=不可解对于某些输入。 无论多少（有限的）时间，你给你的算法，它永远是错的一些输入。
NP-硬〜=超多项式运行时间（假设P！= NP）。 这是手工波浪，但基本上NP难意味着它至少是硬如NP中最难的问题。
当然，还有那些NP-硬不属于不可判定（=是可判定）的问题。 任何NP完全问题将是他们中的一个，说周六
有没有不属于NP难问题的不可判定？ 我不这么认为，但它是不容易排除这种可能 - 我没有看到一个明显的论点，即必须有来自SAT减少所有可能的不可判定问题。 有可能是这不是非常有用的一些奇怪的不可判定问题。 但是标准的不可判定问题（停机问题，说的）是NP难问题。
Answer 2:
一个NP是， 至少是很难，因为任何NP完全问题的一个问题。
因此，一个不可判定的问题可能是NP难问题。 一个问题是NP难的，如果它的甲骨文将使容易解决NP完全问题（即在多项式时间内可解）。 我们可以设想一个不可判定的问题，即，鉴于它的甲骨文，NP完全问题很容易解决。 例如，显然每一个解决停机问题，Oracle还可以解决一个NP完全问题，所以每图灵完备的问题也是NP-很难在这个意义上，一个（快）甲骨文它将使解决NP完全问题微风。
因此图灵完备的不可判定问题是NP难问题的一个子集。
Answer 3:
不可判定的问题如图灵停机问题仅仅是NP难。
<---------NP Hard------>
|------------|-------------||-------------|------------|--------> Computational Difficulty
|<----P--->|
|<----------NP---------->|
|<-----------Exponential----------->|
|<---------------R (Finite Time)---------------->|
在该图中，该小管示出了重叠NP和NP-硬且其示出了NP-完整性，即组的那些NP以及NP难题。
不可判定的问题是它没有解决的，哪些不是在NP NP难的问题。
文章来源: Relationship between NP-hard and undecidable problems
