(轉載自CUP magazine 2014年2月號)
— 電腦科學與數學的懸案（P=NP？）
請勿誤會，我不是寫今年提名奧斯卡獎電影《百萬獎金夢，Nebraska》，而是憶起若干年前我寫過一篇影評《A Beautiful Mind》，是一個關於數學家John Nash的故事。那位女編輯收稿後來電，說我沒寫出整齣戲的一個最大漏洞！我大吃一驚，甚麽漏洞？她說戲中連一台道具PC也沒出現過！
我問她為甚麼數學家一定要用電腦？她答電腦的運算比人腦快得多啊！沒有電腦怎研究數學？我再問她：你知道數學是研究甚麼的嗎？她沒答下去便敷衍掛了線。
今天舊事重提，真的，不知為了甚麽，只是內心有點悶納，覺得一件正常不過的事情，某些人也會產生錯覺，往往把問題變了本末倒置，以偏概全，最近例如普選應有公民提名、不懂中文也有資格當香港大學校長、北區幼稚園近區優先入學……等等也惹來躁音，香港人的邏輯和意識形態何時脫了軌，這社會何時變得如此荒謬！我當然曉得不要和豬打架的道理 —— 豬很骯髒，和牠們糾纏，一定會弄髒自己；豬隻日日無所事事，和牠們打架，更會令牠們很開心。
說回正題，當年女編輯的提問，其實她只是像一般人心理，習慣把電腦神化。雖然目前PC性能和速度確實已大增，加上網絡無比威力，電腦更被神化不足為奇。但直到今天，很多人還未有認清一個事實：電腦無論有多大、多快和多厲害，始終也只不過是一種工具！
數學大致可分應用數學和純數兩大類。應用數學研究的，是找algorithm（運算法則）來解決問題，找到了才輸入電腦運算、找答案；就算現今拓展Big Data和人工智能的藍圖中，已進入了用電腦去找algorithm的新階段，但這些途徑還是建立在先要由人想出來的嚴謹數學統計學（Mathematical Statistics）基礎上，電腦本質上依然是一種工具。至於純數學家，包括John Nash1在內，研究範疇更抽象，他們一生也許只致力去證明（prove）一些命題，甚至要憑空想像一些新命題去證明另一些命題，電腦一直幫不到忙。而且，幾千年來涵衍數學的歷史過程中，電腦不是必需品，人腦創造力才是一切；電腦相反地才是由數學衍生出來的產物。舉一個簡單例子：我們今天只要在計算機上一按√這個鍵，數字的二次方根馬上顯示出來，有些連∛、∜和x-n鍵也有，但運算√的algorithm是人想出來，和計算機無關。（雖然沒有計算機今天絕大部份人便不懂把數字開方！）
最近十年有些改變，超級電腦這工具愈來愈重要，不時輔助催生一些數學和科學上嶄新發現，尤以用在運算大量實時模擬（realtime simulation）和迅速核實（verification）數據的用途上，揭開人類一直追求的生命秘奥，也難怪一般人產生錯覺愈深，神化了電腦。
但到底，數學家是努力去prove一些命題達至solve一些難題，電腦是擅長verify和應用答案，以上可算是數學與電腦關係粗略描述。自然地，我們會繼續問：電腦的角色將來可不可以取代數學家？這便帶出另一基本問題：世上所有難題可有解決方案？這便是Clay Mathematics Institution在千禧年時列出當代七2大未解難題之一 —— P versus NP難題。能解答者可獲獎金一百萬美元，故亦稱為Millennium Prize Problem（千禧大獎難題）。‧
P vs. NP是電腦科學與數學領域中最重要的懸案，源自數學家Stephen Cook在1971年發表的一份影響深遠數學文章〈The complexity of theorem-proving procedures〉，探究當數學家要prove一個定理時需要經過一些什麽複雜程序，背後目的當然是指望將來怎樣才能令電腦代替人腦思維活動，Cook的野心不可謂不大。今年七十五歲的他，當時卻料不到這文章引伸出另外一個更深層次近乎哲學問題，成為今天在電腦科學研究Computational Complexity Theory中最具爭議，懸而未決的命題！
用簡單兩句話概述這千禧大獎難題的核心：假若每個難題的答案也可以「迅速地」用電腦來核實（verify），那末，那些難題是否也可以「迅速地」用電腦來找到答案？
詳盡一點來解釋。世界上有兩類難題（大多指一切牽涉需要大量decision-making的，但並不排除以外還有一些更難的難題, Hard-Problem）：有一類我們已找到一些合適的algorithm放進電腦運算便可「迅速地」得到答案，統稱為P難題；另外一類難題，我們還未找到可以「迅速地」解決問題的algorithm，但如果可以提供一些「疑似」答案，電腦便可「迅速地」核實是否正確，這類統稱為NP難題。例如：耳熟能詳的Travelling Salesman問題——怎樣找出一條最短路線，售貨員便可訪問多個指定城市而不會重叠，或把一個過千位的數子分解因數（factorization），或把一百名女子與一百名男子以各人嗜好匹配全部可能性等，這些問題表面看來簡單直接，一直試下去便是，但當以上例子中所定的城市數目、數位和人數一旦多起來，答案便未能「迅速地」4找到；verify答案卻依然能「迅速地」核實到。
用數學公式來表達P vs. NP難題，就是「P=NP？」，意思是 P（很「迅速地」solve到的） 和NP（很「迅速地」verify或check到的）這兩類難題是否同屬一類？
很明顯，P一定是 NP的子集（subset）。在全部NP難題中，撇除了P那些已找到答案的以外，還有些甚麽剩下？沒有的話，P=NP便成立，也即是世上沒有不能解決的難題！有的話，剩下的可能還有一類NP題，先姑稱之為NP-Complete。NP-Complete的概念更抽象但絕對重要，這類是指全部NP難題中任何一個NP難題也可分拆和簡化（reduced）出來的子NP難題，一層一層地簡化下去， NP難題的子子孫孫（統稱NP-Complete）愈來愈多，這本是一個四十年前Cook的純理論臆度，現今數學家卻發現，愈來愈多本是check到而找不到答案的某些NP難題也可以簡化成一大堆NP-Complete之後，用上超級電腦運算，最終可以solve到，例如DNA排列怎樣與樣本匹配、蛋白質的縲紋怎樣最優化，和甚至男女為何會「相愛」這大問題，上文的男女匹配也是NP-Complete問題之一！最終，我們同樣地要問：還有沒有解決不到的NP-Complete難題嗎？有，就是P≠NP，世上一定是有不可能解答的難題；沒有，就等於說P=NP=NP-Complete，任何難題也能解決，連其餘五條千禧大獎難題也可以解決，獎金升至六百萬美元呢！
最後，將來有沒有人能解答到P vs. NP難題4我們不知道，肯定的是，如那日子來臨，不論答案是=或≠，對一切影響人類文明事物包括電腦科學、數學、機械人、密碼學、生物學、哲學、政治學、經濟學、多媒體處理，……等等會面臨一次翻天覆地巨變，這世界會很不一樣，但我們的Mind一定更美麗！（完）
1 John Nash是研究純數中的博奕論，其後他的理論在日常生活中尤以經濟、軍事和政治活動上大派用場，1994年獲諾貝爾經濟學獎。
2現已剩下六條： 2003年，蘇聯數學家Grigori Perelman成功解答其中一條Poincare Conjecture，但他拒絕接受一百萬美元的獎金！
3以上我多次用「迅速地」這字眼，代替數學上說的Polynomial Time，而P正是Polynomial Time的縮寫。P類難題就是指電腦可以在Polynomial Time之內有效地找到答案，Polynomial Time不是快，是含「有限之年」的意
4 P vs. NP科普讀物，趣味性濃的是Lance Fortnow的《The Golden Ticket》，2013；最詳盡是Richard Lipton的《P = NP and Gödel’s Lost Letter》，2010
