※ 引述《mabus (CodeINCEPTION)》之铭言： : 能不能用白话一点的方式解释？在wiki里有看没懂呀...。 : 若这个问题解决了，有什麽影响吗？ : 本身不是学CS的，可以的话能否推荐书籍呢？ : 先谢谢各位了！ 这个大概没什麽书会讨论吧... 你说你不是学 CS 的那这篇就尽量不放太多专有名词进去 P = NP 的意义是这样的 我们现在有一类问题叫做 P 有另一类问题叫做 NP P 的问题就是解决它所需时间随着问题大小只成多项式成长 (例如问题大小的三次方或五次方成长等等) NP 的问题就是给我问题和一个答案我可以很快的检查这是不是真的是这问题的答案 (同样这里的很快是指多项式成长) P = NP 问题就是问说这两类问题到底是不是一样的 之所以这是难题的原因是 NP 里有一大类问题被叫做 NP-Complete (NP完全) 目前最好的解法所需要的时间都随着问题大小增加而成指数成长 找不到多项式成长的解法 但也无法证明它不存在这种解法 这代表当我们想要解决一个稍微大一点的问题时目前暂时没有很快的解法存在 以其中一个问题 旅行推销员问题 为例 它需要我们在一张地图上找出经过所有城市正好一次再回到出发点的最短路线 最简单的想法就是所有路线都去试试看 那试的次数就是城市数的阶乘 用一些技巧可以把试的次数降到指数成长 但是目前仍然找不到多项式成长的做法 也证明不出不存在这种做法 虽然 P = NP 是个很大的问题 但是看起来又好像没有那麽难 这是因为所有的 NP-Complete 问题有种一个串一个的性质就是 如果你找到其中一个问题的多项式成长做法之後 你可以一个串一个地给出所有 NP-Complete 问题的多项式成长做法 最後再串到所有 NP 问题也都能给出多项式成长做法 於是你就证明了 P = NP 反过来如果你证明了其中一个问题不能有这种做法的话 那麽你便找到了一个问题是属於 NP 但不属於 P 的 於是证明了 P≠NP 无论哪一个你都会在历史上留名的 (附带一笔一百万镁的奖金 XD) 之所以现在许多计算机理论家会这麽想要解决它也是因为 NP-Complete 问题实在很多 英文维基上就列出了至少一两百个属於 NP-Complete 的问题 去年的这个时候也有一个叫 Vinay Deolalikar 的家伙提出了可能是 P≠NP 的证明 (後来被其他专家挑出几个重大错误 他现在还在改) 影响的话其实个人认为刚证出来时多半是理论上的影响 毕竟它要的是多项式成长 如果是以问题大小的一百次方成长也算 但一百次方实际上很难有什麽实质上的影响 但当更进一步的研究之後 NP-Complete 问题这种一个串一个的性质很容易发生某处一个小进步就扩展到全部 这时一些依靠这些问题这种强度的使用就变得不可靠了 例如最常提的就是密码学上的应用 若 P = NP 被证明之後许多这些应用都会变得不安全 (像是这里面最常提的 RSA 所依靠的质因数分解 这个问题目前只已知是 NP 连是不是 NP-Complete 都不知道 但如果 P = NP 被证明的话它一样会遭殃) 反过来如果证明了 P≠NP 那我们可以放心的说这些问题要完美解决没招 於是可以专心的研究它们的近似演算法 (就是能给出接近完美的做法 这可以快很多) 这方面的研究现在就已经很多了 (因为现在许多状况证据都让大家认为 P≠NP 应该是对的 所以与其去撞这堵大墙不如先去做一些能够做的实质性进展) -- 嘛我知道这篇文章稍微用点严格的方式来挑可以有一堆毛病啦 (像是 NP-Complete 的定义性质 以及我故意完全不提 co-NP 和 NP-hard 等等) 不过看在这是篇给外行人看的文章就先这样就好... -- 'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.92