证明NP复杂性

Question

我正在学习如何证明某事是NP。在Thomas Cormen的算法书介绍中，他指出某事是NP，如果给出某个问题的解决方案，你可以在多项式时间内验证它是正确的。

假设问题是2x+9=55，让我们假设我不知道需要多长时间才能找到正确的x值，但解决问题的算法返回了解决方案23。然后，为了证明它是NP，我只需要把23插回方程中，看看这是否需要一个多项式时间，得到55？谢谢

Answer 1

是；如果你能在多项式时间中检查每个正确的和这个问题的每个实例的每个不正确答案的正确性，那么这个问题是NP。

Answer 2

向@Mehrdad答案添加信息：

注意，NP代表非确定性多项式时间-这意味着根据定义-问题在NP中，当且仅当它可以由非确定性图灵机多项式求解。

这相当于说，在标准计算模型(RAM机器/确定性图灵机器)中，你可以在多项式时间内验证答案(就像@Mehrdad回答的那样)。等价性的证明在定义的等价性的维基百科页面中进行了描述

奖金：
"在图灵机上可验证(多项式)的一切是否也可多项式求解"的问题和"在非确定性图灵机多项式上可求解的一切是否在确定性图灵机器多项式上也可求解"的问题也是等价的。
答案是未知的，这个问题被称为P与NP问题，这是计算机科学中最重要的开放问题。

Answer 3

虽然上面的问题涵盖了NP性的最后一步，也许也是最可识别的一步，但有三个基本步骤可以表明问题处于NP中。

1. 决策问题：你能把你的问题变成决策问题吗？在方程问题的情况下，决策问题是"是否有一个x使得2x+9=55？"？

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

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

这就是为什么你知道你的问题完全在NP中。