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

Question

它写在一本书中 - "如果问题A是NP完全的,那么存在一个非确定性的多项式时间算法来解决A".但到目前为止,我知道'是' - NP完全问题的解决方案可以在多项式时间内"验证".我真的很困惑.可以使用非确定性多项式时间算法"解决"NP完全问题吗？

Answer 1

这两件事情基本相同,并且基于两种不同但相当的NP定义.

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

1. 通过确定性图灵机在多项式时间内验证.(如果问题和'验证',您可以回答验证是否在多项式时间内对问题是正确的).
   示例:给定一个图形,并且您想检查其中是否存在哈密顿路径 - 验证者可以是路径.一旦你拥有它,你可以很容易地检查路径是否确实是哈密尔顿.
2. 由非确定性图灵机在多项式时间内求解.(存在M可以多项式解决问题的非确定性图灵机)

由于NP-Complete的定义 - 如果它是NP-Hard AND并且在NP中,则问题是NP完全,每个NP-Complete问题也是NP - 并且两者都是正确的.

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

1. 语言L是NP如果每个x中L有一句话z这样说|z|是多项式|x|,并且存在在多项式时间内运行一些确定性图灵机M-使得对于每x及其配套z,:M(x,z) = true if and only if x is in L
2. 如果存在可以在多项式时间内解决问题的非确定性图灵机,则问题在于NP.形式上,L如果存在非确定性图灵机,则该语言在NP中M(x) = true if and only if x is in L