作者 | Shalitha Suranga

譯者 | 彎月    責(zé)編 | 張文

出品 | CSDN（ID：CSDNnews）

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

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

P/NP 問(wèn)題

 

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

P 類問(wèn)題

P 類問(wèn)題指的是所有可以由一個(gè)確定型圖靈機(jī)在多項(xiàng)式表達(dá)的時(shí)間內(nèi)解決的問(wèn)題。簡(jiǎn)單來(lái)說(shuō)，P 類問(wèn)題就是能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題。舉個(gè)例子，冒泡排序就是 P 類問(wèn)題，因?yàn)樵撍惴ǖ臅r(shí)間復(fù)雜度為 O (n2)，不是指數(shù)級(jí)的。

NP 類問(wèn)題

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

P=NP?

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

大多數(shù)人都認(rèn)為 P≠NP，但是沒(méi)有人能證明。如果有人能夠證明 P=NP，那么就會(huì)極大地推動(dòng)計(jì)算機(jī)的發(fā)展，因?yàn)槲覀兛梢酝ㄟ^(guò)更快的算法來(lái)解決搜索問(wèn)題，而且人們無(wú)需機(jī)器學(xué)習(xí)的算法，也能解決很多困難的決策問(wèn)題。

單向函數(shù)

 

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

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

最快的矩陣乘法算法

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

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

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

多項(xiàng)式整數(shù)分解

 

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

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

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

參考鏈接：

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

---