與其調查，不如撞吓密碼

調查醜聞，議員和官員最擅長成立一個乜乜調查委員會，傳召「涉案」人等，從各項證供和證據抽絲剝繭，推敲事件的來龍去脈。換句話說，跟偵探查案沒有分別。

看過偵探劇的觀眾知道，查案是非常困難而且峰迴路轉的，擾攘一輪之後，通常真兇都不是原來的疑兇。換句話說，調查出來的結果，醜聞主角通常都是「清白」的，即使不是毫無過錯，最終也能置身事外。

亦即是說，如果你想「釘死」某人，成立調查委員會是徒然的，最好另找途徑。我提議闖入他的電郵信箱，直接揪出黑材料，令他不得不認。

然而，闖入電郵信箱先要拆解他的密碼，豈不比成立調查委員會更難？我今天就要說明，拆解密碼其實不比調查困難，有數學根據的。

我問你，這篇文章多少字？不想自己數，可以叫電腦幫你。整份報紙多少字？用電腦數，也是易如反掌。全世界報紙今天總共出了多少字？用電腦數，可能用上幾分鐘，甚至幾小時，終可得出一個答案。數字數這條問題，對電腦來說是「容易」的，資料多了 n 倍，處理時間增加 n 倍，就是這麼簡單。有些問題比較複雜，資料多了 n 倍，處理時間增加 n² 倍；更複雜的，處理時間可以增加 n¹⁰ 倍。一般人看來，一條 n¹⁰ 倍問題比一條 n 倍問題困難得多，但從電腦學角度，它們的難度屬於同一級數，叫 P 級。所有 P 級問題都是「容易」的，一般應用程式有的功能，例如搜尋、排序等，都屬 P 級，這些功能可以放進日常軟件，因為不論資料多寡，處理時間都在「可以接受」範圍之內。

一條 n⁹⁹ 倍問題也「可以接受」？對，從電腦學角度，n⁹⁹ 倍問題與 n 倍問題都屬 P 級，理論上都是「容易」的，難不倒電腦。很明顯，有些問題比 P 級更難，不是 n 的多少次方可以匹敵。

拆解密碼就是這樣一條難題。假設，你從江湖人士口中得知唐英年的電郵密碼由四個小楷英文字母組成，你可以寫條程式，由 aaaa，aaab，aaac …… 試至 zzzy，zzzz，總共 26⁴ 個組合。正在編寫程式之際，江湖人士來電，唐英年剛剛改密碼，現在變成八個小楷英文字母，程式需要改寫，由 aaaaaaaa 試至 zzzzzzzz，總共 26⁸ 個組合；密碼長度是原來的 2 倍，處理時間是原來的 26⁴ 倍！這是假設密碼只由小楷英文字母組成，否則擴展得更快。很多問題如拆解密碼一樣，除了逐個試，想不到更有效方法；這些逐個試的問題屬於 NP 級，難度比 P 級高一截。唐英年若把密碼繼續加長，很快，電腦便沒可能在「可以接受」的時間內估中。

NP 級未算最難，最難的叫 NP-Hard 級。我的數學不夠精，未能在這裏舉出含具體數字的例子。數學家經已證明，很多經典電腦遊戲都是 NP-Hard 的，我不是遊戲迷，有印象的包括俄羅斯方塊、食鬼、孖寶兄弟、Donkey Kong、Doom、Starcraft，還有很多其他；說它們 NP-Hard，未必是遊戲規則複雜，而是極難計算出最佳玩法。最近甚至有人證明物理學都是 NP-Hard 的，物理學骨子裏就是根據物體運行的數據推敲主宰其運行的方程式，與偵探查案或調查委員會根據各方證據推敲真相的做法如出一轍；我雖不能確切證明，但醜聞調查應該不比物理學或電腦遊戲容易，如果物理學和很多電腦遊戲都是 NP-Hard，醜聞調查至少也是 NP-Hard。

換句話說，醜聞調查（NP-Hard）比破解密碼（NP）困難。與其成立乜乜調查委員會，不如嘗試破解密碼，解不開的話，調查「定罪」的機會只會更渺茫。

最後補充，P 和 NP 代表什麼？一些數學的專有名詞，寫出來也無甚意思。一般讀者大可這樣想，人生遇到的問題有三種：「有可能」解決的（P = Possible），「無可能」解決的（NP = Not Possible），還有「無可能……咁難？！」解決的。

（2012 年 3 月 17 日 信報副刋）