《计算复杂性:现代方法》——第2章 NP和NP完全性 2.1 类NP
本节书摘来自华章计算机《计算复杂性:现代方法》一书中的第2章,第2.1节,作者 [美]桑杰夫·阿罗拉(Sanjeev Arora),博阿兹·巴拉克(Boaz Barak),译 骆吉洲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
第2章
NP和NP完全性
如果你曾玩过填字游戏,那你一定知道从头开始游戏远比验证其他人给出的答案难得多。同样,自己动手做数学家庭作业远比阅读和理解老师给的答案难得多。区别在于,寻找填字游戏的答案和解数学题是创造性劳动。验证答案相对容易的原因是其他人已经完成了创造性劳动。
2.1 类NP
现在,我们定义复杂性类NP,由此将“可被高效验证的解”这一直觉概念形式化。在第1章,我们曾说一个问题是“可被高效求解的”,如果它可以被图灵机在多项式时间内求解。于是,问题的解是“可被高效验证的”,指的是该问题的解可以在多项式时间内得到验证。由于图灵机每步只能读一个位,因此这意味着给定的解不能太长——至多是输入长度的多项式。