P/NP 問題是計算復(fù)雜度領(lǐng)域至今未解決的一個問題。人們一直試圖找到一個問題的答案：「我們能否在合理時間內(nèi)有效解決所有的計算問題？」

什么是合理的時間？實際上在宇宙終結(jié)之前能夠解決的問題都算在合理時間內(nèi)。然而許多問題似乎都難以在合理的時間內(nèi)解決，這需要用數(shù)學(xué)來證明這些問題的難度。

2021 年的一項研究解答了上述問題，該研究證實：很大一部分問題都很難有效解決。

華盛頓大學(xué)的 Paul Beame 評價這項研究稱：「就像攀登山峰一樣，這項研究是計算理論研究路上的一個落腳點?！?/p>

該研究的三位研究者：計算機(jī)科學(xué)家 Srikanth Srinivasan（左）、Nutan Limaye（右上）和 Sébastien Tavenas。

該研究考慮的問題只涉及加法和乘法，但當(dāng)這些問題僅限于以特定方式（加法和乘法的某種交替模式）解決時，它們就變得非常困難。

令人驚訝的是，該研究沒有使用新的框架或工具，相反，作者設(shè)法繞過了由普林斯頓高等研究院數(shù)學(xué)學(xué)院教授 Wigderson 與耶路撒冷希伯來大學(xué) Noam Nisan 合作數(shù)十年的工作中描述的數(shù)學(xué)障礙。

研究者之一、丹麥奧胡斯大學(xué)的 Srikanth Srinivasan 說：「我們意識到有一種非常簡單的方法可以繞過這個障礙。并且，如果用這么簡單的方法就能做到我們認(rèn)為不可能的事情，那么肯定能找到更好的方法?！?/p>

重要的問題

計算機(jī)出現(xiàn)之后，科學(xué)家們發(fā)現(xiàn)計算機(jī)算法可以解決許多問題，但有時這些算法花費(fèi)的時間太長——比實際計算時間更長。

他們開始懷疑有些問題是本質(zhì)上難度太大，無論問題的規(guī)模是大是小都難以解決。例如在圖中，一個重要的問題是確定是否存在一條哈密頓路徑，即存在一條路徑通過且僅通過每個頂點一次。增加點（和邊）的數(shù)量應(yīng)需要更長的時間來確定是否存在這樣的路徑，但即便是最好的算法，隨著圖規(guī)模的增加，花費(fèi)的時間也會呈指數(shù)增長，這使得解決這個問題變得不切實際。

計算機(jī)科學(xué)家試圖證明，任何能夠以某種方式有效解決某類問題中一個難題的算法，都可以轉(zhuǎn)化為對其他類似困難問題的解決方法，他們稱這一類問題為 NP 問題。

當(dāng)然，也有很多看起來不難的問題，不需要花費(fèi)太多時間來解決。這些問題中的很多在某種意義上也是等價的，這類問題被稱為 P 問題。他們認(rèn)為 NP 問題確實比 P 問題更難，并且 NP 問題永遠(yuǎn)無法有效解決。但如果沒有證據(jù)，這種想法就可能是錯誤的。

因此，計算機(jī)科學(xué)家們開始尋找方法來證明 NP 問題確實更難，這需要證明 NP 問題必須要指數(shù)級的時間才能解決，但證明這一點并不容易。

多難才算「困難（hard）」？

設(shè)想一組只需要加法和乘法的特定問題。例如，給定一組點，可以僅通過加法和乘法，用關(guān)于點的數(shù)據(jù)來計算所有可能的哈密頓路徑（如果存在的話）。

隨著問題規(guī)模的增加，一些算術(shù)問題（如計算哈密頓路徑）需要更多的時間。1979 年，哈佛大學(xué)的 Leslie Valiant 證明許多算術(shù)問題在「難度」上是等價的，而其他的則在「沒有難度」上是等價的。計算機(jī)科學(xué)家后來以他的名字命名這兩類問題——分別是 VNP 和 VP。

和 P 與 NP 問題一樣，我們無法證明 VNP 問題的難度，我們只知道 VNP 問題比 NP 問題更難，因為它建立在后者的基礎(chǔ)之上，例如計算路徑首先需要確定路徑是否存在。

「這比 NP 難，因此證明這很困難應(yīng)該更容易」，Shpilka 說道。

在隨后的幾十年中，計算機(jī)科學(xué)家在 VP 與 VNP 問題上取得的進(jìn)展比他們在 P 與 NP 問題上取得的進(jìn)展要大得多，但其中大部分僅限于 Valiant 創(chuàng)建的稱為代數(shù)復(fù)雜性的子領(lǐng)域。在 Limaye、Srinivasan 和 Tavenas 最近的工作之前，他們?nèi)匀缓茈y判斷是否存在一般意義上的算術(shù)問題。

調(diào)整多項式

這項新工作有助于探究計算機(jī)科學(xué)家思考加法和乘法問題的方式。從數(shù)學(xué)上講，這些問題完全可以寫作多項式的形式（例如 x^2 + 5y + 6），這些多項式由相加和相乘的變量組成。

對于任何特定問題，例如計算哈密頓路徑，你可以構(gòu)建一個表示它的多項式。例如你可以用一個變量來表示每個點和邊，這樣當(dāng)添加更多點和邊時，就可以向多項式添加更多變量。

為了證明計算哈密頓路徑這樣的算術(shù)問題很困難，就需要證明當(dāng)添加更多點和邊時，相應(yīng)的多項式需要以指數(shù)時間解決更多操作。例如，x^2 需要一次操作（x * x），而 x^2 + y 需要兩次操作（x * x 然后加上 y）。操作的數(shù)量稱為多項式的大小。

但是多項式的大小很難確定。例如多項式 x^2 + 2x + 1。它的大小似乎為 4（兩次乘法和兩次加法），但是該多項式可以重寫為兩個和的乘積，(x + 1)(x + 1)，它的操作數(shù)更少——兩次加法，一次乘法。通常，隨著問題的規(guī)模擴(kuò)大和將更多變量添加到多項式中，數(shù)學(xué)變換可以幫助簡化和縮小其規(guī)模。

在 Valiant 的研究幾年之后，計算機(jī)科學(xué)家找到了一種方法，可以使問題的大小更易于分析。為此，他們提出了一個稱為「深度（depth）」的屬性，它指定多項式在和與乘積之間切換或交替的次數(shù)。例如，多項式 x^2 + 2x + 1 的深度為 2，因為它是乘積之和（如 x^2 和 2x）。相比之下，表達(dá)式 (x + 1)(x + 1) 的深度為 3，因為它的深度與 0 + (x + 1)(x + 1) 相同，按照乘積之和計算。

為了簡化多項式，計算機(jī)科學(xué)家將它們限制為一種固定形式，并具有稱為「恒定深度」的屬性，其中和、乘積的模式不會隨著問題的增長而改變。這使得它們的大小更加固定，多項式的大小會隨著其深度的增加而減小。某個恒定深度的表達(dá)式稱為公式。恒定深度讓多項式的研究取得了更多進(jìn)展。

神奇的「深度」

1996 年， Nisan 和 Wigderson 的一篇論文專注于解決矩陣乘法的問題，他們用兩種方式簡化了這個問題。首先，他們用恒定深度的公式來表示它——深度為 3。其次，他們只考慮了具有某種簡單結(jié)構(gòu)的公式，其中每個變量的最大指數(shù)為 1，這使得原問題成為「多線性」問題。

計算機(jī)科學(xué)家已經(jīng)發(fā)現(xiàn)，某些問題可以轉(zhuǎn)換為相對簡單的集合多線性（set-multilinear）結(jié)構(gòu)，代價是多項式的大小呈次指數(shù)增長（與指數(shù)增長的增長率相當(dāng)）。

Nisan 和 Wigderson 隨后表明了隨著矩陣的擴(kuò)大，矩陣乘法問題需要指數(shù)級的時間來解決。換句話說，他們證明了一個重要的問題是困難的，為證明一類問題都是困難的做出了努力。然而，他們的結(jié)果只適用于具有簡單的、集合多線性結(jié)構(gòu)的公式。

Leslie Valiant

增加多項式的深度往往會導(dǎo)致其大小減小。隨著時間的推移，計算機(jī)科學(xué)家使這兩個屬性之間的權(quán)衡變得更精確。他們表明，將兩個深度級別添加到深度 3、集合多線性多項式可以平衡其集合多線性結(jié)構(gòu)的大小增益。如果深度 5 的結(jié)構(gòu)化公式需要指數(shù)時間，那么具有一般、非結(jié)構(gòu)化性質(zhì)的深度 3 公式也是如此。

Srikanth Srinivasan 等人的新工作表明，矩陣乘法問題的深度 5 集合多線性公式確實以與指數(shù)級速度增長。這意味著一般的深度 3 公式也需要指數(shù)時間。隨后他們證明類似的規(guī)律適用于所有深度（不止是 3 和 5）。有了這種關(guān)系，他們就證明了對于同一個問題，任何深度的一般公式的大小都會隨著問題的規(guī)模而以指數(shù)速度增長。

他們還表明用一個恒定深度的公式表示矩陣乘法是很難的，無論該深度是多少。

該研究的結(jié)果首次提供了對于算術(shù)問題何時是「困難」的一般理解——當(dāng)它不能用恒定深度的公式表示時即為困難。矩陣乘法的具體問題已知是 VP 問題。并且已知 VP 問題在不限于恒定深度時相對容易，因此結(jié)果得出恒定深度為問題「困難」的來源。

VNP 問題是否比 VP 問題更難？新結(jié)果并沒有直接說明這一點，他們只表明恒定深度公式很難。但這仍然是證明 VNP 問題不能等價于 VP 問題的重要里程碑。

對于更大的 P 與 NP 問題，我們現(xiàn)在可以對有一天能找到答案更加樂觀了。畢竟為了解決困難的問題，我們首先需要知道哪些方向是無望的。