剧照 | 唐人街探案3

作者 | Shalitha Suranga

译者 | 弯月  出品 | CSDN

在现实生活中，很多难题的解决方案都用到了计算机科学的基础理论。例如， Git 分布式版本控制系统建立在图论、数据结构和密码学等之上。然而，每个理论中也存在非常具有挑战性的问题。

伟大的计算机科学家们已经解决了很多理论难题。例如，快速排序法和合并排序法都是有效的大型列表排序算法。然而，就像其他研究领域一样，计算机科学也有自己的神秘之处。许多计算机科学家都在努力寻找这些谜团的解决方案。但是，计算机科学界仍然还有一些至今仍未解决的难题，因为科学家无法证明他们的答案是正确的，而且大多数其他的计算机科学家也不接受他们的答案。

P/NP 问题

 

计算机可以解决各种计算问题。在计算机科学中，计算问题可以分为几大类，比如 NL、P、NP、PSPACE 等。

P 类问题

P 类问题指的是所有可以由一个确定型图灵机在多项式表达的时间内解决的问题。简单来说，P 类问题就是能在多项式时间内解决的问题。举个例子，冒泡排序就是 P 类问题，因为该算法的时间复杂度为 O(n²)，不是指数级的。

NP 类问题

相反，NP 类问题指的是需要由一个非确定型图灵机在多项式表达的时间内解决的问题。简单来说，NP 类问题的算法比 P 类问题慢很多。著名的 NP 类问题：旅行家推销问题（TSP）。即有一个推销员，要到 n 个城市推销商品，他要找出一个包含所有n个城市的环路，这个环路的路径小于 a。我们知道这个问题如果单纯的用枚举法来列举的话会有(n-1)! 种解，已经不是多项式时间的算法了(注：阶乘的复杂度比多项式高得多)。但重要的是，如果给定一个解，我们可以在多项式时间内验证该解是否正确。

P=NP?

也就是，我们能在多项式的时间内验证某个 NP 类问题的解是否正确，可是我们却不知道 NP 类问题是否存在一个多项式时间的算法，能够保证在多项式时间内求出问题的解（注意，这里是不知道，不是不存在）。所以这就引出了一个难题：NP 类问题= P 类问题？即，是否所有能在多项式时间内验证解的正确性的问题，都是具有多项式时间算法的问题呢？

大多数人都认为 P≠NP，但是没有人能证明。如果有人能够证明 P=NP，那么就会极大地推动计算机的发展，因为我们可以通过更快的算法来解决搜索问题，而且人们无需机器学习的算法，也能解决很多困难的决策问题。

单向函数

 

单向函数（One-way function）是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定型图灵机计算）。

单向函数是否存在，至今仍然是计算机科学中的一个未解难题。事实上，如果能够证明单向函数存在，也就可以证明在 P/NP 问题中，P 不等于 NP。但是，P 不等于 NP 的假设并不能直接推出单向函数的存在。

最快的矩阵乘法算法

矩阵乘法广泛用于科学计算、计算机图形学和模式识别领域。因此，许多计算机科学家都在努力寻找更快的算法。甚至还出现了一些与硬件相关的特殊矩阵乘法算法，例如分布式和并行算法。

施特拉森算法（Strassen algorithm）是一个计算矩阵乘法的算法，是第一个时间复杂度低于 O(n3)的矩阵乘法算法。此外，最近还有一些研究论文提出了渐进时间复杂度更低的矩阵乘法算法。

然而，最快的矩阵乘法算法尚未问世。另外，现有的算法也没有明确的渐进时间复杂度。

多项式整数分解

 

整数分解又称质因数分解，是指将一个正整数分解成几个因数的乘积，且这些因数必须是质数。如果给定的整数非常小，则对于计算机而言，分解过程非常简单。但是，给出一个大整数（100 位数以上的整数），找出它们的因数就不是那么容易了。目前，我们还没有发明出多项式时间的算法，在非量子计算机上进行更快的整数分解。不过，量子计算机上已经发明了 Shor 整数分解算法。

事实上，许多现代密码系统就利用了现有整数分解算法的这个弱点，比如 RSA 公钥加密算法。如果有人能够找到快速解决整数分解问题的方法，则所有基于 RSA 的加密技术都将失效。冯诺依曼体系结构的经典计算机不可能破解 RSA-2048 算法，因为因数分解需要的时间超过了宇宙的寿命。

但是，最新研究成果表明，量子计算正在以更快的速度赶上当今加密标准。科学家已经证明，2000 万个量子比特只需要短短 8 小时就可以破解 2048 位的 RSA 加密。然而，问题在于，我们还没有这样的计算机。

参考链接：

https://medium.com/swlh/the-biggest-unsolved-problems-in-computer-science-f24b79008252

-End-