你真的理解什么是P,什么是NP吗?.doc
《你真的理解什么是P,什么是NP吗?.doc》由会员分享,可在线阅读,更多相关《你真的理解什么是P,什么是NP吗?.doc(4页珍藏版)》请在三一文库上搜索。
1、你真的理解什么是P,什么是NP吗?编者按:说起复杂度,相信不少人会想到Jeff Dean面试Google时的一个笑话,面试官问:如果P=NP成立,你能推导出哪些结论?年轻的Dean面不改色:P=0或N=1。虽然这个经典段子令人回味无穷,但你真的理解什么是P,什么是NP吗?对于计算机来说,做什么事是容易的,做什么事是几乎不可能完成的,这些问题构成了计算复杂度的核心。如果计算机科学家希望能用一个叫做“复杂度”的东西对问题进行分类,那么一个问题有多困难?这会是他们需要面对的基本任务。所谓“复杂度”,它可以被看作是包含所有计算问题的一系列组,组间划分依据是解决具体问题所耗费的资源是否在某个固定数量以下
2、,这里的资源可以是时间,也可以是内存。以一个玩具问题为例:123,456,789,001是不是质数?对于这个问题,计算机科学家可以用现有算法快速得到答案123,456,789,001不是质数。无论这个数字是否会变得越来越大,算法计算所需资源会一直在可控范围内,不会突破天际。那么,新的问题产生了:它的质因子有哪些,除了1和本身,它还能被哪些数整除?通常情况下,我们认为它和上个问题拥有不同的“复杂度”。验证一个数是不是质数很简单,但找出它的所有质因子就很困难。目前,算法还不能在短时间内解决这个问题,除非我们已经有了成熟的量子计算机。“复杂度”本身存在大量不同的类别,但在大多数情况下,我们还无法证明
3、这一类“复杂度”和那一类“复杂度”有哪些显著不同。这些差异可能是微妙的,也可能是明显的。因此对于大多数人来说,明确分类各种复杂度也是一个艰巨的挑战。什么是P?代表:多项式时间复杂性类(Polynomial time)简介:所有P问题都能被经典计算机(非量子计算机)轻松解决。详细说明:如果一个问题是P问题,那么它必须满足在多项式时间nc内验证一个算法问题的实例是否有解 ,其中n是输入长度,c是个常数。典型问题:这个数是否是个质数?两点之间的最短路径是什么?研究热点:P=NP是否成立?如果成立,它将颠覆计算机科学,并使大多密码学内容在一夜之间失效(当然大多数人还是认为P!=NP)。什么是NP?代表
4、:非定常多项式时间复杂性类(Nondeterministic Polynomial time)简介:如果给出了一个解,所有NP问题都能被经典计算机快速验证。详细说明:如果一个问题有一个解,且能在多项式时间内证明这是个正解,那么这就是个NP问题。例如,假设问题的输入是字符串X,我们的目标是验证问题的解为“是”,那么我们就需要一个证明字符串Y,用它在多项式时间内验证答案确实是“是”。典型问题:分团问题。想象一个带边和点的图形,我们把它当成Facebook的社交网络,一个节点代表一个用户,如果两个用户是朋友关系,那么两个节点通过边连接。一个clique表示整个社交网络中的一个子集,其中所有人都是彼此
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 理解 什么是 NP
链接地址:https://www.31doc.com/p-3381708.html