一本书中写道——“如果问题 A 是 NP-Complete,则存在解决 A 的非确定性多项式时间算法”。但据我所知,"is"——NP 完全问题的答案可以在多项式时间内“验证”。我真的很困惑。能否使用非确定性多项式时间算法“解决”NP 完全问题?
最佳答案
这两个东西基本相同,并且基于两个不同但等效的 NP 定义。
NP 中的每个问题(语言)都必须是:
- 通过确定性图灵机在多项式时间内进行了验证。 (给定一个问题和一个“验证”,您可以在多项式时间内回答该验证是否正确)。
示例:给定一个图,您想要检查其中是否存在哈密尔顿路径 - 验证者可以是路径。获得路径后,您可以轻松地检查它是否确实是哈密尔顿路径。 - 由非确定性图灵机在多项式时间内求解。 (存在非确定性图灵机
M
可以多项式地解决问题)
由于根据 NP-Complete 的定义 - 如果问题是 NP-Hard 且在 NP 中,则该问题是 NP Complete,因此每个 NP-Complete 问题也是 NP - 并且两者都是正确的。
请注意,这两个声明基本上基于 NP 的两个等效定义:
- 语言
L
在 NP 中,如果对于L
中的每个x
都有一个单词z
使得|z|
是|x|
中的多项式,并且存在一些以多项式时间M
运行的确定性图灵机 - 这样对于每个x
及其匹配的z
,:M(x,z) = true 当且仅当 x 在 L 中
- 如果存在可以在多项式时间内解决问题的非确定性图灵机,则该问题属于 NP 问题。形式上,如果存在非确定性图灵机使得
M(x) = true 当且仅当 x 在 L 中
,则语言
L
在 NP 中
关于algorithm - NP 完全 - 在非确定性多项式时间内可解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20638165/