algorithm - NP 完全 - 在非确定性多项式时间内可解

Question

一本书中写道——“如果问题 A 是 NP-Complete，则存在解决 A 的非确定性多项式时间算法”。但据我所知，"is"——NP 完全问题的答案可以在多项式时间内“验证”。我真的很困惑。能否使用非确定性多项式时间算法“解决”NP 完全问题？

Answer 1

这两个东西基本相同，并且基于两个不同但等效的 NP 定义。

NP 中的每个问题(语言)都必须是:

1. 通过确定性图灵机在多项式时间内进行了验证。 (给定一个问题和一个“验证”，您可以在多项式时间内回答该验证是否正确)。
   示例:给定一个图，您想要检查其中是否存在哈密尔顿路径 - 验证者可以是路径。获得路径后，您可以轻松地检查它是否确实是哈密尔顿路径。
2. 由非确定性图灵机在多项式时间内求解。 (存在非确定性图灵机 M 可以多项式地解决问题)

由于根据 NP-Complete 的定义 - 如果问题是 NP-Hard 且在 NP 中，则该问题是 NP Complete，因此每个 NP-Complete 问题也是 NP - 并且两者都是正确的。

---

请注意，这两个声明基本上基于 NP 的两个等效定义:

1. 语言 L 在 NP 中，如果对于 L 中的每个 x 都有一个单词 z 使得|z| 是 |x| 中的多项式，并且存在一些以多项式时间 M 运行的确定性图灵机 - 这样对于每个 x 及其匹配的 z，:M(x,z) = true 当且仅当 x 在 L 中
2. 如果存在可以在多项式时间内解决问题的非确定性图灵机，则该问题属于 NP 问题。形式上，如果存在非确定性图灵机使得 M(x) = true 当且仅当 x 在 L 中
，则语言 L 在 NP 中