Is P=NP?
5 months ago
- #P-vs-NP
- #complexity-theory
- #cryptography
- 复杂性理论根据计算资源（如时间和空间）对问题进行分类。
- 大O符号通过增长率（例如O(1)、O(n)、O(n²)、O(2ⁿ)）对算法进行分类。
- P（多项式时间）问题可以快速解决，而NP（非确定性多项式时间）问题具有可验证的解决方案但可能难以解决。
- NP完全问题是普遍存在的难题；解决其中一个问题可能解决所有NP问题。
- NP难问题至少与NP完全问题一样难，但可能无法快速验证。
- P=NP将颠覆密码学并通过使优化问题变得简单而彻底改变人工智能。
- 现代密码学依赖于单向函数，如果P=NP，这些函数将变得过时。
- 作者做了一个关于P=NP的梦，引发了对数字安全的存在性思考。