3

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

假设问题是 2x + 9 = 55，假设我不知道找到正确的 x 值需要多长时间，但是解决问题的算法返回了解决方案 23。然后证明它是 NP，我只需将 23 代入等式，看看这是否需要多项式时间并给我 55？谢谢。

4

3 回答 3

4

是的; 如果您可以在多项式时间内检查此问题的每个实例的每个正确和每个错误答案的正确性，那么问题就在 NP 中。

于 2012-12-01T04:56:56.810 回答
2

向@Mehrdad 答案添加信息：

请注意，NP 代表Nondeterministic Polynomial time - 这意味着根据定义 - 当且仅当它可以通过Non-deterministic Turing Machine以多项式方式解决时，问题才属于 NP 。

这相当于说在标准计算模型（RAM 机器/确定性图灵机）中 - 您可以在多项式时间内验证答案（如 @Mehrdad 回答）。定义等价的维基百科页面中描述了等价的证明

奖励：
“在图灵机上可验证（多项式）的所有事物是否也是多项式可解决的”和“在非确定性图灵机多项式上可解决的所有事物是否也可在确定性图灵机多项式上解决”的问题也是等价的。
答案尚不清楚，这个问题被称为P vs NP 问题，这是计算机科学中最重要的开放性问题。

于 2012-12-01T08:10:26.567 回答
1

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

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

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

  3. 验证：您能否在多项式时间内验证证书。通过在多项式时间内进行验证，您知道问题不是 NP-Hard。一些验证步骤可能是：是 xa 数字吗？X 等于 55-9 的二分之一吗？

这就是你如何知道你的问题完全在 NP 中。

于 2019-04-23T04:21:27.103 回答