計算機(jī)科學(xué)界至今未解決的四大難題

一只頂 2021-02-07

展開全文

作者：Shalitha Suranga

譯者：彎月

責(zé)編：張文

出品：CSDN（ID：CSDNnews）

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

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

P/NP 問題

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

P 類問題

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

NP 類問題

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

P=NP?

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

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

單向函數(shù)

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

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

最快的矩陣乘法算法

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

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

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

多項式整數(shù)分解

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

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

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

參考鏈接：

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

未來智能實驗室的主要工作包括：建立AI智能系統(tǒng)智商評測體系，開展世界人工智能智商評測；開展互聯(lián)網(wǎng)（城市）云腦研究計劃，構(gòu)建互聯(lián)網(wǎng)（城市）云腦技術(shù)和企業(yè)圖譜，為提升企業(yè)，行業(yè)與城市的智能水平服務(wù)。

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：一只頂 > 《待分類》

舉報/認(rèn)領(lǐng)