NP难与不可判的问题之间的关系

Question

对于不可判断的问题和NP难题之间的关系,我有点困惑.NP难题是否是不可判定问题的一个子集,或者它们是否相同且相同,还是它们不具有可比性？

对我而言,我一直在与朋友争辩说,不可判断的问题是NP难题的超集.存在一些不是NP难以解决的问题但是不可判定的问题.但我发现这个论点很弱,而且有点困惑.是否存在不完全的NP完全问题.在NP hard中有任何问题是可判定的吗？

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

Answer 1

不可判定=对某些输入无法解决.无论你给算法多少(有限)时间,在某些输入上总是会出错.

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

当然存在NP难的问题并不是不可判定的(=可判定的).SAT说,任何NP完全问题都将是其中之一.

有难以解决的问题不是NP难的吗？我不这么认为,但要排除它并不容易 - 我没有看到一个明显的论点,即必须从SAT减少所有可能的不可判定的问题.可能会有一些奇怪的不可判定的问题,这些问题不是很有用.但标准的不可判定的问题(比如停止问题)是NP难的.

Answer 2

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

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

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