【CSDN 編者按】世界很大，人才很多，但是難題也不少……
作者 | Shalitha Suranga
譯者 | 彎月 責編 | 張文
出品 | CSDN（ID：CSDNnews）
在現實生活中，很多難題的解決方案都用到了計算機科學的基礎理論。例如， 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:http://medium.com/swlh/the-biggest-unsolved-problems-in-computer-science-f24b79008252
程式員如何避免陷入“內卷”、選擇什么技術最有前景，大陸開發者現狀與技術趨勢究竟是什么樣？快來參與「2020 大陸開發者大調查」，更有豐富獎品送不停！
