《Factor Man》︰證明P=NP後,你要如何向全世界宣布?

以計算複雜度理論著名難題為主題的小說

kayue
kayue
Mar 16 · 10 min read

假如發現了幾乎可破解全世界所有密碼,甚至大幅改善人類生活的技術,你會怎樣做?這大概就是小說《Factor Man》要講的故事。但要了解這個故事為何有趣,必須先了解電腦科學中懸而未決的「P vs. NP問題」,本文會先介紹這個問題,最後才有點劇透(會附上警示)。

嚴格來說,書中的「因數俠」(Factor Man自稱名字參考了Iron Man,所以我這樣翻譯)發現了可以快速解決NP問題的演算法,因此那是個P=NP的世界——不明白不要緊,以下我會解釋。

問題的分類

P vs. NP問題所屬的領域稱為「計算複雜度理論」(computational complexity theory,以下簡稱「複雜度理論」),粗略來說,這是研究問題有多難解決的學科。當然,電腦科學研究的問題需要可以用演算法解決,而這領域的專家就是分析相關演算法去把各種問題分類。

首先要注的是,此處「問題」不是「一個問題」,而是「一組(相關的)問題」,例如加法問題——「計算 m+n 的答案」——其實由無限多個問題組成︰1+1=?, 1+2=?, 1+3=? … 但這些問題可用同一個演算法處理,只需要輸入不同的值便會得出相應問題的答案。

加法問題屬於函數問題(function problem),即計算函數值的問題,而本文主要討論決策問題(decision problem),這類問題只有「是」或「否」兩個可能答案,例如解答「n是否質數?」的質數判斷問題(primality test)。

至於因數分解問題——「尋找n的所有因數(或最小質因數)」——雖是個函數問題,但可以改寫成決策問題「n是否有一個小於m但大於1的因數?」,這兩個版本的因數分解問題可以互相轉換。

複雜度理論中,問題按其解決的演算法分成多個類別,而P vs. NP問題就涉及P和NP兩個類之間的關係,一般會認為屬於P的問題比較容易處理、可以在較短時間內解決,而NP中的問題難以解決、需要花很長時間才能找到答案。「P=NP」代表一些看似較難以解決的問題原來沒那麼困難,而「P≠NP」則表示兩類問題之間有道界線。

接下來我會嘗試解釋P和NP到底是甚麼。

量度效率

複雜度理論中把決策問題分類的方法,是按照解決問題的演算法的效率決定,如果我們找到演算法可以快速解決一個問題,這個問題可視為容易解決;相反,如果目前解決某個問題的演算法非常慢,這個問題應算是難以解決。

但應怎樣判斷「快」和「慢」呢?如果比較運行演算法至得出答案的時間,在不同電腦上運行會得出不同結果,即使訂立一部「標準電腦」也非常不方便——電腦硬件發展迅速,難道每幾年要重新計時嗎?而且現代電腦中央處理器包含很多指令集,程式的效率也取決於處理器支援甚麼指令集。

粗略來說,判斷演算法效率的標準是看它運算所需的「步數」,不過也不是看實際數字,而是跟輸入數值的關係——輸入的數值越大,往往涉及更多運算步驟。量度(二進制的)輸入值大小的單位是位元,也就是數值寫出來有多長(例如十進制的13寫成二進制就是1101,是個4位元的數字)。此外需要注意的是,這個「步數」通常是上限,即在最壞情況、需要最多時間運算時的數字。(在其他情況,我們亦可用平均運算時間量度演算法的效率。)

假設某個演算法在輸入值長度為n時,其運算時間的函數是n²,那就代表輸入10位長的數值需要最多100步就得出答案,輸入50位長的數值則需要最多2500步。

如果解答一個決策問題的演算法所需的時間上限可以寫成多項式,例如n³(n代表輸入值長度),這個決策問題就屬於P——P代表「多項式」(polynomial)——也稱作可以在「多項式時間」內解決,這類問題被視為可以迅速解決。(當然,假如這個多項式的冪次極大,比方說n³¹⁴⁸⁹²⁸⁰⁵,實際上也不能迅速解決,只是一般而言屬於P的問題都有迅速解決的演算法。)

NP問題中的「P」同樣代表多項式,不過並非代表尋找答案的時間,而是驗證答案的時間。面對這一類問題,我們未必能夠迅速判斷答案是「是」抑或「否」,但如果有人找到答案是「是」的話,他就可以給我們一個「證人」,讓我們在多項式時間內驗證。就像數獨(Soduko)遊戲中,只看到迷題的話我們未必能夠很快判斷是否有答案,但如果有人解出了,我們就可以很快驗證答案是否正確。(至於那個「N」其實代表「nondeterministic」,意思涉及另一種較技術性的定義方式,所以在此不解釋。)

以下舉兩個NP問題作為例子︰

  • 因數分解問題︰「n是否有一個小於m但大於1的因數?」假設答案為「是」,即有一個因數k存在而且1<k<m,我們只需要把n除以k,便能驗證它是n的因數。(同樣道理,如果某個質數判斷問題的答案為「否」,我們也有辦法迅速驗證,這類問題稱為Co-NP問題。)
  • 子集和問題︰「給定一個由整數組成的集合,當中是否有一個總和為0的子集?」舉個例,{-3, -1, 2, 4, 6}這個集合是否有一個總和為0的子集?答案為「是」,因為{-3, -1, 4}中的所有數字加起來等如0。任何集合如果有一個總和為0的子集,我們只需要知道那個子集的元素,便可以把它們加起來迅速驗證。
Image Credit: smbc|這則漫畫的笑點在於一個叫做bin packing problem的問題(決策版本)其實是個NP-Complete問題,所以搬運工說可以看一眼就解決的時候,數學家跪求他不要入侵自己的電郵。

P和NP的關係

由於所有屬於P的決策問題都能在多項式時間內解決,這些問題都能在多項式時間內驗證,因此它們都是NP問題,換言之,P是NP的一個子集,記為「P ⊆ NP」。而P vs. NP問題則是︰P和NP是否相等?

如果P=NP的話,而且找到一個能快速解決NP問題的演算法的話,將會有大量實際應用,例如一些排序、配對問題都屬於NP問題,對科學(解決某些蛋白質摺疊問題)以至數學亦有深遠影響,例如不少加密技術依賴「驗證密鑰」與「尋找密鑰」兩個問題難度的不對稱,而且數學證明本身就是容易驗證、難以尋找的東西,因此我們甚至可以得到一個自動解決數學問題的演算法。

此處需要介紹多一類稱為「NP-Complete」的問題,這是NP問題中最困難的一類——只要解決到一個NP-Complete問題就可以在多項式時間內解決其他NP問題。因此,只要有人找到可以在多項式時間內解決NP-Complete問題的演算法,就代表所有NP問題都屬於P,從而證明了P=NP。

也許因為P=NP的世界美好得難以置信——以及其他技術理由——學界主流意見傾向相信P≠NP。複雜度理論專家William Gasarch分別在2002、2012及2019年進行三次問卷調查,以了解這個領域的專家對P vs NP問題的立場,以下是調查結果

Ind = Independent(獨立於公理系統,未有註明是哪個系統), DC = Don’t Care, DK = Don’t Know.

以上大概就是P vs NP問題的背景,接下來終於可以談《Factor Man》(劇透警告)。

證明P=NP後的行動指南

我今年初在Gasarch的網誌上得悉《Factor Man》這本小說,他那篇網誌的標題就是〈假如你證明了P=NP後會做甚麼?我會重Matt Ginsberg的《Factor Man〉(What would you do if you showed P=NP? I would reread Factor Man by Matt Ginsberg),他表示︰

雖然專家都這樣說,我就放心訂書。小說我讀得不多,不覺得這本特別精彩,但至少讀得非常暢快——認得出書中出現的真實人名時更會會心微笑,例如著名複雜度理論及量子運算專家Scott Aaronson,他的出場時間不短(我也有訂閱他的網誌)——又沒有那些愚蠢的錯誤,雖然涉及一位中國特務的內容寫得一般,那些內心讀白似乎流於刻版印象(例如多次明言鄙視美國的資本主義)。

書中Factor Man先透過網誌宣告自己能夠在多項式時間內解決SAT問題(最早被證明屬於NP-Complete的問題),從而能夠在短時間進行因數分解,他公開接受網民遞交數字給他分解因數,但只限由兩個質數相乘的數字,上限由5位元開始,每天增加一個位元,直到2019年6月10日分解255位元為止。那一天他會開始接受競投,一個月後(即2019年7月10日)勝出者可獲得獨家使用其技術一年,一年後(2020年7月10日)美國政府會得到這項技術,再一年後(2021年7月10日)技術會公開,他亦會披露自己身份。

Factor Man希望在公開技術前先給各界一段時間準備,期間盡力隱藏身份,但同時這項重要技術不免引起各國政府興趣,不斷追查Factor Man真身。對於應否如此公開改變世界的技術我仍有保留(至少不應先獨家給大企業和美國政府),而且弄一場盛大的「亮相派對」也未免太高調,不過這個問題與我無關,我讀小說只是為了過癮。

話說回來,我翻查RSA因數分解挑戰的記錄發現,這個挑戰第一項的數字RSA-100已有330位元,於1991年被分解,而20年前已有人可以分解140位、463位元的數字,我不清楚現時的個人電腦能否在一天內完成運算,但至少書中提到沒有足夠電腦分解128位元的數字應不準確。無論如何,這個問題不影響書中主要情節,而其他情節如Aaronson被懷疑是Factor Man、他質疑Factor Man只不過證明了因數分解問題屬於P、成功投得Factor Man技術授權的公司用該技術騷擾競爭對手等亦寫得不錯。

我猜對科技、電腦有興趣的讀者,應該會覺得這本小說有趣。

延伸閱讀

如果讀完後對複雜度理論有興趣,可以追蹤以下媒體及網誌︰

  • 《Quanta Magazine》︰一個主要報導數學、電腦科學、物理學及生物學新聞的媒體,有不少關於複雜度理論的文章,數學內容也非常好。
  • Shtetl-Optimized︰Scott Aaronson的網誌,通常有點長,未必跟複雜度理論有關,但也有些不錯的內容。
  • Computational Complexity Blog︰William Gasarch與Lance Fortnow的網誌,後者亦著有介紹P vs. NP問題的《The Golden Ticket: P, NP and the Search for the Impossible》。

kayue

Written by

kayue

《關鍵評論網》編輯,最想寫的還是數學。https://hk.thenewslens.com/author/kayue

More From Medium

Related reads

Related reads

Related reads

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade