NP-hard与不可判定问题的关系

Question

我对不可判定问题和NP困难问题之间的关系感到有点困惑。NP难题是否是不可判定问题的子集，或者它们是相同和相等的，还是它们不具有可比性？

对我来说，我一直在和我的朋友们争论，不可决定的问题是NP困难问题的超集。将会存在一些问题，这些问题不是NP困难的，但无法确定。但我发现这个论点是站不住脚的，而且有点困惑。是否存在无法确定的NP-完全问题？在NP hard中有什么问题是可以决定的吗？？

一些讨论会有很大的帮助！谢谢!

Answer 1

不可判定=某些输入不可解。无论你给你的算法多少(有限的)时间，它在某些输入上总是错误的。

NP-hard ~=超多项式运行时间(假设P != NP)。这是手挥手，但基本上NP-hard意味着它至少和NP中最难的问题一样难。

当然，有一些问题是NP-hard的，也不是不可判定的。任何NP-complete问题都是其中之一，比如SAT。

是否存在非NP-hard的不可判定问题？我不这么认为，但排除它并不容易-我看不到一个明显的论点，即必须从SAT减少到所有可能无法决定的问题。可能会有一些奇怪的无法决定的问题，这些问题并不是很有用。但是标准的不可判定问题(比如停顿问题)是NP难的。

Answer 2

NP-hard是一个至少和任何NP-完全问题一样难的问题。

因此，不可判定的问题可能是NP-难的。如果一个问题的预言会使解决NP-完全问题变得容易(即在多项式时间内可解)，则该问题是NP-难的。我们可以想象一个不可判定的问题，如果给它一个神谕，NP-完全问题将很容易解决。例如，很明显，解决停顿问题的每个先知也可以解决NP-完全问题，因此每个图灵完全问题也是NP-困难的，因为(快速)先知将使解决NP-完全问题变得轻而易举。

因此，图灵完全不可判定问题是NP-难问题的一个子集。

Answer 3

不可判定问题例如图灵停顿问题只是NP-Hard问题。

                   <---------NP Hard------>
|------------|-------------||-------------|------------|--------> Computational Difficulty

|<----P--->|

|<----------NP---------->|

|<-----------Exponential----------->|

|<---------------R (Finite Time)---------------->|

在这个图中，小管道显示了NP和NP-Hard的重叠，并显示了NP -完备性，即NP和NP-Hard问题的集合。

不可判定问题是指无解且不在NP中的NP难问题。