证明NP问题的复杂度

Question

我正在学习如何证明某些问题属于NP。在Thomas Cormen的算法导论中，他指出，如果给定一个问题的解决方案，您可以在多项式时间内验证其正确性，则该问题属于NP。

比如说，问题是2x + 9 = 55，假设我不知道找到正确的x值需要多长时间，但是一个算法返回了解23。那么，要证明它属于NP，我只需要将23代入方程中，看看这是否需要多项式时间并且得到了55。谢谢。

- roverred

---

我认为这个问题更适合在http://cstheory.stackexchange.com/上讨论。 - Seth Battin

@SethBattin：不完全是，但也许对于http://cs.stackexchange.com会更合适。 - user541686

啊哈，那是我打算链接到的另一个网站。 :) 而且它似乎是该网站此刻最新的问题。 - Seth Battin

这怎么可能被认为是离题的？！它在 Stack Overflow 上问了一个计算机科学问题，天哪！！ - user541686

Answer 1

是的，如果你能在多项式时间内检查每个正确和不正确答案的正确性，并且对于这个问题的每个实例都能做到这一点，那么该问题就属于NP问题。

- user541686

---

不！你正在描述一种算法，而不是一个问题！NP完备性是定义在问题上而非算法上的。一个问题是NP完备的，当且仅当它满足以下两个条件：（1）属于NP问题集合；（2）可以通过多项式时间规约从NP问题集合中的每个问题得到。 - amit

然而，请注意，答案仍然不完整，如果您可以在多项式时间内检查每个正确和每个不正确的答案以解决此问题的每个实例，则该问题属于 NP。 - amit

@amit：是的，我忘了提到这一点，因为它已经在问题中了……如果你愿意，请随意编辑。 - user541686

我认为只有在多项式时间内可以验证“是”的答案，问题才属于NP类？如果答案是“否”，它可能会永远运行但仍然属于NP类。我的理解是否正确？我指的是确定性机器。 - goat

@rambocoder：我觉得你在这里有些混淆了（或者可能是我的回答表述不清）。如果有人给你一个图并说“这个图中是否存在哈密顿回路？”，那么“否定”类型的答案确实被认为不能在P时间内验证。但是，“这条路径是否确实是哈密顿回路？”的问题确实可以在P时间内验证，无论答案是“是”还是“否”。我觉得你在谈论前者，而我在谈论后者……或者我只是困惑了？ - user541686

Answer 2

补充@Mehrdad的答案：

注意，NP代表“非确定性多项式时间” - 这意味着根据定义 - 只有通过非确定性图灵机可以在多项式时间内解决问题，该问题才属于NP。

这等价于说，在标准计算模型（RAM机器/确定性图灵机）中，您可以在多项式时间内验证答案（就像@Mehrdad回答的那样）。证明等价性的方法在维基百科关于定义等价性的页面上有说明。

奖励：
“在图灵机上可验证的所有内容（多项式时间）也可以在图灵机上多项式时间内解决”的问题以及“在非确定性图灵机上可解决的所有问题都可以在确定性图灵机上多项式时间内解决”的问题是相等的。
答案尚未知晓，该问题被称为P与NP问题，它是计算机科学上最重要的未解决问题。

- amit

Answer 3

以上问题涵盖了NP难度的最后一步，也是最具标识性的一步，但要证明一个问题属于NP难度有三个基本步骤。

1. 决策问题：你能把你的问题转化为一个决策问题吗？对于方程问题，决策问题将是“是否存在一个x，使得2x + 9 = 55？”

2. 证书：你能够确定你的决策问题的答案吗？同样，在方程问题的情况下，答案可能是x = 23。

3. 验证：你能在多项式时间内验证证书吗？通过在多项式时间内验证，你知道这个问题不是NP困难问题。一些验证步骤可能是：x是一个数字吗？X是否等于55-9的一半？

这就是你知道你的问题完全属于NP的方式。

- braedenrose