P/NP 问题

在计算机科学中, P/NP 问题是著名的未解难题, 指的是以下问题:

•	是否有 P = NP? 换言之, P 问题是否与 NP 问题相同?

这里, P 问题是指能在多项式时间复杂度内可以找到解的问题, 而 NP 问题是指给定一个解, 能在多项式时间复杂度内可以验证其是否正确的问题.

当然, 所有 P 问题都是 NP 问题. 因此, 上述问题可以重新表述为:

•	NP 问题是否都是 P 问题? 换言之, 是否所有 NP 问题都能在多项式时间内解决?

在目前, Turing 机是主流的计算模型. 想要使用 Turing 机在多项式时间内解决 NP 问题显得异常困难. 然而, 如果允许使用强于 Turing 机的计算模型, 该问题则更有可能解决.

1后果

如果 P = NP, 那么:

•	密码学里利用 NP 问题的加密手段都能在多项式时间内破解.

•	某些数学猜想将可以被计算机解决, 比如 Riemann 猜想.

•	Stephen A. Cook (1971). “The complexity of theorem-proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158. (doi)