劇照 | 唐人街探案3

作者 |?Shalitha Suranga

譯者 | 彎月??出品 | CSDN

在現(xiàn)實生活中，很多難題的解決方案都用到了計算機科學的基礎(chǔ)理論。例如， Git 分布式版本控制系統(tǒng)建立在圖論、數(shù)據(jù)結(jié)構(gòu)和密碼學等之上。然而，每個理論中也存在非常具有挑戰(zhàn)性的問題。

偉大的計算機科學家們已經(jīng)解決了很多理論難題。例如，快速排序法和合并排序法都是有效的大型列表排序算法。然而，就像其他研究領(lǐng)域一樣，計算機科學也有自己的神秘之處。許多計算機科學家都在努力尋找這些謎團的解決方案。但是，計算機科學界仍然還有一些至今仍未解決的難題，因為科學家無法證明他們的答案是正確的，而且大多數(shù)其他的計算機科學家也不接受他們的答案。

P/NP 問題

?

計算機可以解決各種計算問題。在計算機科學中，計算問題可以分為幾大類，比如 NL、P、NP、PSPACE 等。

P 類問題

P 類問題指的是所有可以由一個確定型圖靈機在多項式表達的時間內(nèi)解決的問題。簡單來說，P 類問題就是能在多項式時間內(nèi)解決的問題。舉個例子，冒泡排序就是 P 類問題，因為該算法的時間復雜度為 O(n2)，不是指數(shù)級的。

NP 類問題

相反，NP 類問題指的是需要由一個非確定型圖靈機在多項式表達的時間內(nèi)解決的問題。簡單來說，NP 類問題的算法比 P 類問題慢很多。著名的 NP 類問題：旅行家推銷問題（TSP）。即有一個推銷員，要到 n 個城市推銷商品，他要找出一個包含所有n個城市的環(huán)路，這個環(huán)路的路徑小于 a。我們知道這個問題如果單純的用枚舉法來列舉的話會有(n-1)! 種解，已經(jīng)不是多項式時間的算法了(注：階乘的復雜度比多項式高得多)。但重要的是，如果給定一個解，我們可以在多項式時間內(nèi)驗證該解是否正確。

P=NP?

也就是，我們能在多項式的時間內(nèi)驗證某個 NP 類問題的解是否正確，可是我們卻不知道 NP 類問題是否存在一個多項式時間的算法，能夠保證在多項式時間內(nèi)求出問題的解（注意，這里是不知道，不是不存在）。所以這就引出了一個難題：NP 類問題= P 類問題？即，是否所有能在多項式時間內(nèi)驗證解的正確性的問題，都是具有多項式時間算法的問題呢？

大多數(shù)人都認為 P≠NP，但是沒有人能證明。如果有人能夠證明 P=NP，那么就會極大地推動計算機的發(fā)展，因為我們可以通過更快的算法來解決搜索問題，而且人們無需機器學習的算法，也能解決很多困難的決策問題。

單向函數(shù)

?

單向函數(shù)（One-way function）是一種具有下述特點的單射函數(shù)：對于每一個輸入，函數(shù)值都容易計算（多項式時間）；但是對于一個隨機的函數(shù)值，算出其對應的輸入?yún)s比較困難（無法在多項式時間內(nèi)使用確定型圖靈機計算）。

單向函數(shù)是否存在，至今仍然是計算機科學中的一個未解難題。事實上，如果能夠證明單向函數(shù)存在，也就可以證明在 P/NP 問題中，P 不等于 NP。但是，P 不等于 NP 的假設(shè)并不能直接推出單向函數(shù)的存在。

最快的矩陣乘法算法

矩陣乘法廣泛用于科學計算、計算機圖形學和模式識別領(lǐng)域。因此，許多計算機科學家都在努力尋找更快的算法。甚至還出現(xiàn)了一些與硬件相關(guān)的特殊矩陣乘法算法，例如分布式和并行算法。

施特拉森算法（Strassen algorithm）是一個計算矩陣乘法的算法，是第一個時間復雜度低于 O(n3)的矩陣乘法算法。此外，最近還有一些研究論文提出了漸進時間復雜度更低的矩陣乘法算法。

然而，最快的矩陣乘法算法尚未問世。另外，現(xiàn)有的算法也沒有明確的漸進時間復雜度。

多項式整數(shù)分解

?

整數(shù)分解又稱質(zhì)因數(shù)分解，是指將一個正整數(shù)分解成幾個因數(shù)的乘積，且這些因數(shù)必須是質(zhì)數(shù)。如果給定的整數(shù)非常小，則對于計算機而言，分解過程非常簡單。但是，給出一個大整數(shù)（100 位數(shù)以上的整數(shù)），找出它們的因數(shù)就不是那么容易了。目前，我們還沒有發(fā)明出多項式時間的算法，在非量子計算機上進行更快的整數(shù)分解。不過，量子計算機上已經(jīng)發(fā)明了 Shor 整數(shù)分解算法。

事實上，許多現(xiàn)代密碼系統(tǒng)就利用了現(xiàn)有整數(shù)分解算法的這個弱點，比如 RSA 公鑰加密算法。如果有人能夠找到快速解決整數(shù)分解問題的方法，則所有基于 RSA 的加密技術(shù)都將失效。馮諾依曼體系結(jié)構(gòu)的經(jīng)典計算機不可能破解 RSA-2048 算法，因為因數(shù)分解需要的時間超過了宇宙的壽命。

但是，最新研究成果表明，量子計算正在以更快的速度趕上當今加密標準。科學家已經(jīng)證明，2000 萬個量子比特只需要短短 8 小時就可以破解 2048 位的 RSA 加密。然而，問題在于，我們還沒有這樣的計算機。

參考鏈接：

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

-End-