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

Factor Man
Matt Ginsberg

假如發現了幾乎可破解全世界所有密碼，甚至大幅改善人類生活的技術，你會怎樣做？這大概就是小說《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的子集，我們只需要知道那個子集的元素，便可以把它們加起來迅速驗證。

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問題的立場，以下是調查結果︰

以上大概就是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），他表示︰

The novel Factor Man is about what someone who has solved P=NP does. I won’t tell you how it goes, but they deal with the issue intelligently. So if I solved P=NP then I would first re-read it, and think through if I would do that, or modify what is done, or what. Its a good start.

雖然專家都這樣說，我就放心訂書。小說我讀得不多，不覺得這本特別精彩，但至少讀得非常暢快——認得出書中出現的真實人名時更會會心微笑，例如著名複雜度理論及量子運算專家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》。