第86章 NP问题
第86章 NP问题 (第1/3页)
“我先给您讲讲什么是P，NP问题。”对方虽然是个机车技术专家，但对信息学了解未必很深，徐少东决定从最基本的概念开始讲起，“首先说清楚一个概念，时间复杂度，在信息学里指的是当问题的规模扩大后，算法需要的时间增长多快。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。而NP问题是指在多项式的时间内可以验证一个解的问题。”
赵友亮皱着眉认真想了一会，说道：“那P问题就是NP问题的子集嘛，基本概念倒是理解了，不过还是太抽象。”
“那我打个比方啊，比如这趟火车上的几百个人，如果要证明这里边有您认识的人，那么最笨的办法就是把每个人都带到你面前，让你一个一个辨认，而你可能一眼就能作出判断，验证所需的时间非常的短。”
“嗯，你这么一说就形象多了。”赵友亮好像有点明白这是怎么回事。
“既然验证答案的时间是多项式级的，那么是否能找到一种办法，同样在多项式的时间内完成这个问题，即P问题是否能等同于NP问题。很多年来，要证明P=NP或者P≠NP，这在信息学里就等同于证明物理学里的大统一理论和数学中的歌德巴赫猜想。而NP完全问题就是NP问题中时间复杂程度最高的问题，所有NP类问题都约化到NP完全问题，只要解决了它，就能解决所有的NP问题。”
“你这么一说，我有点想起来了，这不就是逻辑电路的可满足性问题嘛。”赵友亮哈哈一笑，学术的讨论使他暂时抛下了心里的烦心事，“如果一旦P=NP证明成立，那这个世界可就天翻地覆了。”
“是的，首先被推翻的就是密码学，现实中用的好多加密算法，核心都归结于P不等于NP上，像基于大质数相乘的RSA算法。其次是数学，寻找一个证明和验证一个证明变得同样简单，错误的猜想将瞬间被推翻。然后是运筹学，整数规划、旅行商问题，包括我正在研究的运行图编制问题也将被轻松
（本章未完，请点击下一页继续阅读）