16

我对不可判定问题和 NP 难题之间的关系有点困惑。NP难问题是不可判定问题的子集，还是它们只是相同且相等，还是它们不可比较？

对我来说，我一直在和我的朋友争论，不可判定的问题是 NP 难题的超集。会存在一些在 NP 中不难但无法确定的问题。但是我发现这个论点很弱并且有点困惑。是否存在不可判定的 NP 完全问题。NP难有什么问题是可判定的吗？？

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

4

3 回答 3

12

Undecidable = 某些输入无法解决。无论您给算法多少（有限）时间，某些输入总是会出错。

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

肯定有 NP-hard 的问题不是不可判定的（= 是可判定的）。SAT 说，任何 NP 完全问题都是其中之一。

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

于 2012-05-08T09:00:43.440 回答
6

NP-hard 是一个至少与任何 NP-complete 问题一样难的问题。

因此，一个不可判定的问题可能是 NP 难的。如果一个问题的预言机将使解决 NP 完全问题变得容易（即可在多项式时间内解决），则该问题是 NP 难的。我们可以想象一个不可判定的问题，如果给定一个预言机，NP 完全问题将很容易解决。例如，显然每个解决停机问题的预言机也可以解决一个 NP 完全问题，因此每个图灵完全问题也是 NP 困难的，因为它的（快速）预言机将使解决 NP 完全问题成为微风。

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

于 2012-05-08T08:58:05.150 回答
0

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

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

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

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

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

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

在这个图中，那个小管道显示了 NP 和 NP-Hard 的重叠，它显示了 NP-Completeness，即一组既是 NP 又是 NP-Hard 的问题。

不可判定的问题是 NP Hard 问题，它们没有解决方案并且不在 NP 中。

于 2014-02-18T17:21:38.333 回答