本博客参考:
- https://zhuanlan.zhihu.com/p/348250098
- https://zhuanlan.zhihu.com/p/348020672
- https://zhuanlan.zhihu.com/p/260512272
- 以及相关的1-6。
是什么
NP的全称是Non Deteministic Polynomial,是线性所不能判别的问题的集合。
NP这个东西是从哪里来的呢?
起源
NP的提出,是基于图灵机模型的。
什么是图灵机?
图灵机有k条带子,左端有限,右端要多长可以有多长(潜在无限长)。每条带子都按顺序划分了格子,一个格子可以记录一个符号。符号的有限集我们称之为字母表(alphabet) . 每条带子上有一个带头(tape head),可以读取或更改一个格子里的内容。带头可以左右移动,我们规定图灵机的每个步骤中,带头只能向左一格、向右一格或不动。
用最通俗的语言来解释,图灵机是运行在3条带子和寄存器上的符合规则的自动化的机器。
用图灵机解决问题
有了这个机器,怎样才算使用这个机器解决了问题呢?为了简洁,我们目前只限定“判别命题是否为真”这种判别类问题。
当对输入和问题,图灵机运算后,图灵机能停,并且输出判定结果,则称图灵机解决了此问题。
通俗理解,是对于一个命题,图灵机能够不死循环,并且输出判别结果是真是否,那么就说此问题被图灵机解决。
对图灵机的大胆猜测
强邱奇-图灵(CT)论题:任何物理上可实现的计算装置A,都可被图灵机以多项式代价模拟。
再换句话说,任何装置都可以别图灵机以多项式的代价模拟。
不过请注意,这是一个论题,不是结论,是一个猜想。
为了验证此猜想,其举例了三个装置,每一个装置都能用图灵机“代替”,三个装置分别是:1. 任意大的字母表;2.单带图灵机;3.双向图灵机。(感兴趣可以看原帖子,我们只需要理解,此猜想大胆认为任何装置都能被以线性代价图灵机模拟替代。)
图灵机的泛化
该泛化认为,任意一个装置/程序,都可以被看成一个“通用图灵机”,即输入-处理-输出。
以当前我们熟悉的东西举个例子,对于某一个单独的指令,一个主机可以被看成图灵机;一个手机可以被看成图灵机;以及一个程序,也可以被看成一个图灵机。
对图灵机解决问题的复杂度
A reminder,“解决问题”的定义,是图灵机能够判断此命题是否为真。
结合C-T论题,我们把所有具有多项式时间算法的问题认为是同一类,也就是P (Polynomial)类。但凡在这类里面的问题,都被叫做在图灵机上有“高效算法”。
这其实也变相声明了图灵机的计算复杂度上限,是线性问题,也就是复杂度$O(1)、O(n^a)、O(log_a(n))$,其中$a$是常数。
非确定性图灵机
刚刚我们所“熟悉”的图灵机,叫做确定性图灵机。还有一种,叫做非确定性图灵机。二者对比:
换一张:
可以看到,左侧的情况下,对于计算的“搜索” 的效率,不如右侧的高。
这种非确定性的图灵机,通常用来解决存在性问题。NDTM的每一条计算路径试图构造一个存在性证明,若构造成功,在输出带上写1并停机,称该计算是成功的,该终止格局为接受格局;若构造失败,在输出带上写0并停机,称该计算是失败的,该终止格局为拒绝格局;永不终止的计算路径也视为失败的。
看到这里,目前所有的程序,都是左侧的图灵机的泛化,对于右侧的非确定性图灵机,还没有一个物理现实(不过好像量子计算机就是,但是还没实用)。在原帖中,对于非线性复杂度的问题,右侧的非确定性图灵机能够以线性复杂度解决。
所以出现了P类问题Polynomial,即能使用确定性图灵机有高效解决方法的问题;和NP问题Non deterministic Polynomial,不能用确定性图灵机线性判别的问题。
回到现在,网络上的帖子
看到很多视频或者回答说P问题就O()多少的问题,然后复杂度上到O多少,就是NP问题了。
确实说的也不能算错,就是这个NP出现的源头,其实算是说,有没有存在一个“高效算法”在当前这个问题上。
由于现在所有的程序都是确定性图灵机的泛化,所以对于非线性的复杂度问题是不存在“高效算法”的。现在大家也不说deterministic了,只说能否在合理时间下输出结果。这也算概念的引申吧!
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
本系列是开源书C++ Best Practises的中文版,全书从工具、代码风格、安全性、可维护性、可移植性、多线程、性能、正确性等角度全面介绍了现代C++项目的最佳实践。本文是该系列的第四篇。 可维护性 避免使用编译宏 宏在编译之前被预处理器所替换,从而使得…