千禧年七大难题之 P = NP
千禧年七大难题之 P = NP
那么什么是 P 类型的问题
P 类型的问题说的是如果给你 100 张扑克牌你需要找出这一百张扑克牌中最大的那一张, 如果目前你有一百张扑克牌那么你只需要比较 100 -1 次就可以找出最大的那一张扑克牌,现在问题来了如果给你 100万张扑克牌那么你可能需要比较 100万 - 1 次才能找出那张最大的扑克牌!
NP 类型的问题是
NP 类型的问题是如果你有 100万 张扑克牌你可以验证你觉得最大的那张牌是否成立,验证问题比较快。
P 与 NP 的区别在于
-
P 是你不知道最大的那张牌是什么需要从第一张一直比对到最后一张牌 NP 在于你可以猜测某张牌是最大的那一张
假设如果 P = NP 那么
-
我们搭建的 Web 安全将面临雪崩。 P = NP的话Bitcoin就没了,但是随即想到整个世界的货币体系也会随之崩塌。 P 在密码学里面对应了 暴力穷举 ,NP 在密码学里面对应了 字典破解,如果 P = NP 成立那么破解的效率飞速提升。 对应而来的好处会有: 我们就有希望快速计算出某些蛋白质的具体结构,进而找到很多疾病的致病机理从而造福人类。 经济领域的纳什均衡,计算机领域的电路优化,航空领域最优航线的设计等等一系列的问题。 如果 P = NP 被成功证明世界将面临颠覆性的改变。
然而 P = NP
-
从 1971 年至今 P = NP 已经难道了一批又一批的数学家。 最终 P = NP 类问题被收录到了 千禧年七大难题。 无论是证实还是证伪都会有 100万 美元的奖励。