Matrix67: The Aha Moments
·
16 年后重谈 P 和 NP
💡
原文中文，约12300字，阅读约需30分钟。
📝
内容提要
在超市购物时，我和老婆思考如何安全叠放物品。通过对物体重量和承重进行排序，可以找到安全叠放的方案。算法复杂度为O(n²)，而暴力枚举的复杂度为O(n·n!)，后者在数据量大时不可行。P与NP问题探讨了高效解法与验证解法的关系，至今未解。
🎯
关键要点
- 在超市购物时，需要考虑物品的重量和承重，确保安全叠放。
- 给定 n 个物体的重量和最大承重，判断是否可以安全叠放。
- 安全叠放的策略是按物体的重量与承重之和进行排序。
- 如果所有物体的安全系数非负，则存在安全叠放方案。
- 算法的时间复杂度为 O(n²)，而暴力枚举的复杂度为 O(n·n!)。
- O(n·n!) 的算法在数据量大时不可行，计算时间极长。
- P 与 NP 问题探讨了高效解法与验证解法的关系，至今未解。
- P 问题是可以在多项式时间内解决的问题，NP 问题是可以在多项式时间内验证的问题。
- 如果 P = NP，则所有 NP 问题都可以在多项式时间内解决。
- 目前没有找到任何 NP 完全问题的多项式解法，普遍认为 P ≠ NP。
- P = NP 问题是计算机科学领域最大的未解之谜，解决者将获得百万美元奖金。
- 如果 P = NP，许多优化问题将变得易于解决，但也会导致安全隐患。
❓
延伸问答
P与NP问题的核心是什么？
P与NP问题探讨了高效解法与验证解法的关系，核心是能否在多项式时间内找到解与验证解是否等价。
如何判断物体是否可以安全叠放？
通过给定物体的重量和最大承重，按重量与承重之和排序，检验是否所有物体的安全系数非负。
为什么O(n·n!)的算法在数据量大时不可行？
因为O(n·n!)的时间复杂度在数据量增加时增长极快，导致计算时间极长，无法在合理时间内完成。
如果P=NP，会有什么影响？
如果P=NP，许多优化问题将变得易于解决，但也会导致安全隐患，如电子签名和加密算法的失效。
P问题和NP问题的区别是什么？
P问题是可以在多项式时间内解决的问题，而NP问题是可以在多项式时间内验证的问题。
目前是否有已知的NP完全问题的多项式解法？
目前没有找到任何NP完全问题的多项式解法，普遍认为P≠NP。
➡️
