上海財(cái)經(jīng)大學(xué)理論計(jì)算機(jī)科學(xué)研究中心主任
我的研究方向是理論計(jì)算機(jī)。每次我跟別人說自己的專業(yè)時(shí)，大家都會問我一個(gè)問題：你是做硬件還是軟件？
我每次都非常尷尬。因?yàn)槲壹炔皇亲鲇布?，也不是做軟件的。大學(xué)畢業(yè)后十幾年，我就沒有寫過程序。我們?nèi)粘５墓ぷ?，只要一張紙、一只筆就可以了。
理論計(jì)算機(jī)的關(guān)鍵詞不在計(jì)算機(jī)，而在計(jì)算。我們關(guān)注的是計(jì)算的理論。
大家可能前兩年看過一個(gè)電影，叫《模仿游戲》。電影就是以計(jì)算理論的祖師爺——圖靈的生平作為原型。
圖靈在1936年的一篇論文中精確地定義了什么叫計(jì)算。這樣的精確定義有什么意義呢？
一方面，從他原始的初衷來說，有了這樣精確的定義，就可以證明什么東西是不能計(jì)算的。
另外一方面的意義可能對我們的影響更大?，F(xiàn)代計(jì)算機(jī)就是在圖靈機(jī)這樣的數(shù)學(xué)模型基礎(chǔ)上造出來的。雖然計(jì)算機(jī)已經(jīng)被發(fā)明出來了，但計(jì)算的理論還是沿著自身的邏輯發(fā)展，繼續(xù)研究計(jì)算的真相。
什么是計(jì)算的真相呢？
簡單來說，就是我們計(jì)算的能力到了什么程度？計(jì)算的極限又在哪里？什么是可以計(jì)算的？什么是不能計(jì)算的？什么是容易計(jì)算的？什么是不容易計(jì)算的？
計(jì)算其實(shí)是無處不在的。從最深刻最基礎(chǔ)的數(shù)學(xué)到最酷最炫的信息科技應(yīng)用；從最客觀的自然科學(xué)，到我們?nèi)粘Ｉ钪械纳鐣?、?jīng)濟(jì)行為。計(jì)算與它們都有著非常廣泛而本質(zhì)的聯(lián)系。
非常幸運(yùn)，我本人的研究方向恰好與數(shù)學(xué)、科學(xué)、技術(shù)、經(jīng)濟(jì)學(xué)這四個(gè)緯度都有交叉。所以，我的朋友和合作者中既有數(shù)學(xué)家、物理學(xué)家、經(jīng)濟(jì)學(xué)家、也有計(jì)算機(jī)應(yīng)用科學(xué)的學(xué)者以及一線的程序員和工程師們。
其實(shí)這四類人是非常不一樣的，他們之間使用的語言和關(guān)注的東西都很不一樣，彼此很難對話。但是，他們跟我都對話得很好，合作得很好。我覺得這也從一個(gè)角度論證了計(jì)算思維的普適性。
在計(jì)算與數(shù)學(xué)、科學(xué)、技術(shù)、經(jīng)濟(jì)學(xué)這四個(gè)方向的聯(lián)系中，大家對計(jì)算與科學(xué)、技術(shù)的聯(lián)系相對好理解一些。
比如它與科學(xué)方面的聯(lián)系?，F(xiàn)在最火的技術(shù)叫量子信息與量子計(jì)算，就是計(jì)算與物理學(xué)的結(jié)合?，F(xiàn)在這個(gè)領(lǐng)域特別火。不僅各國政府投入了很多資金，很多高科技企業(yè)也加入了。就在最近這短短的一年左右，BAT先后成立了量子計(jì)算與量子信息的實(shí)驗(yàn)室。
計(jì)算與技術(shù)的結(jié)合就更不用說了?，F(xiàn)在的高科技都是以計(jì)算機(jī)科學(xué)的技術(shù)為基本支撐的。包括大家說得特別多的人工智能技術(shù)、區(qū)塊鏈技術(shù)等等。
不過我今天最想講的，是計(jì)算與數(shù)學(xué)、經(jīng)濟(jì)學(xué)的聯(lián)系。
讓我們從數(shù)學(xué)開始。德國偉大的數(shù)學(xué)家希爾伯特有一個(gè)很重要的貢獻(xiàn)。他在1900年巴黎國際數(shù)學(xué)家大會上，提出了23個(gè)數(shù)學(xué)問題。這23個(gè)問題涉及數(shù)學(xué)非常多不同的方向，很大程度上引導(dǎo)了整個(gè)21世紀(jì)數(shù)學(xué)的發(fā)展。
后來很多人試圖解答他的這23個(gè)問題，從而發(fā)展出了很多新的數(shù)學(xué)理論和工具。其中有一些到現(xiàn)在還沒有解出來。
我們今天要講的是他的第10個(gè)問題。第10個(gè)問題，大家非常好理解，尤其對小時(shí)候?qū)W過奧數(shù)或者有孩子在學(xué)奧數(shù)的人來說，很好理解。
就是隨便給你一個(gè)方程，讓你回答這個(gè)方程有沒有整數(shù)解？（編者按：即不定方程可解性）
前段時(shí)間，有個(gè)特殊的方程在我的朋友圈里刷屏了。
這個(gè)方程看起來非常簡潔，也沒有什么特殊的。問題是存不存在三個(gè)正整數(shù)ABC使得這個(gè)方程成立。
這題為什么很有趣呢？
因?yàn)檫@樣的正整數(shù)確實(shí)是存在的，但如果你去算一下的話，我相信你不會很快算出來。因?yàn)樗钚〉囊粋€(gè)正整數(shù)解是長這個(gè)樣子的。具體多少位我也沒數(shù)過。
從這個(gè)例子，大家可以看出。不是所有的問題都可以通過輸入方程，就能把解給找出來。
就像希爾伯特第10問題，雖然已經(jīng)有了答案，但結(jié)果卻不是希爾伯特所希望的。希爾伯特希望找出一個(gè)通用的方法。但我們通過計(jì)算理論證明了通用方法是不存在的。不存在一個(gè)算法，可以給你一個(gè)方程，就能確定地找到一個(gè)解。
這樣一種否定性的回答，有時(shí)候在數(shù)學(xué)中反而具有更加深刻的意義。
計(jì)算的理論現(xiàn)在已經(jīng)發(fā)展得很成熟了。我們大家已經(jīng)知道，哪些問題是可以算的，哪些問題是不能算的。
現(xiàn)在，計(jì)算理論關(guān)注的焦點(diǎn)已經(jīng)從能不能算發(fā)展到了難不難算。也就是計(jì)算的復(fù)雜性問題。
計(jì)算復(fù)雜性怎么理解？意思是我們要用多長時(shí)間來把這個(gè)問題給算出來。
我們再舉一個(gè)奧賽題。這是一張紙，上面有一張圖。你沿著圖上的線畫，但是同一條線不能畫兩次，你能不能把這個(gè)圖一筆畫出來？
如果嘗試所有的畫法，需要很久；如果這個(gè)圖再大一點(diǎn)，就更麻煩了。有沒有一個(gè)簡便的方法呢？
我想很多人會知道這個(gè)簡便的方法。那就是你看每一個(gè)點(diǎn)連接的線是奇數(shù)條還是偶數(shù)條。偶數(shù)條我們就叫偶點(diǎn)，奇數(shù)條叫奇點(diǎn)。如果一個(gè)圖的奇點(diǎn)數(shù)不超過2的話，這個(gè)圖就是可以一筆畫的。
有了這樣一個(gè)簡單的辨別方法，即使這個(gè)圖里有幾百個(gè)點(diǎn)，你也能很快判斷出能不能一筆畫完。
如果我把這個(gè)題稍微換一下，說圖中的每個(gè)點(diǎn)都不能重復(fù)呢？就好比這是一個(gè)游覽圖，每個(gè)點(diǎn)代表一個(gè)景點(diǎn)，你能不能把所有的景點(diǎn)沒有重復(fù)地游覽一遍？
這個(gè)問題在數(shù)學(xué)上稱為哈密爾頓道路問題。當(dāng)然你可以把所有可能的路線圖都走一遍。但如果這個(gè)圖的點(diǎn)數(shù)超過幾百的話，即使用現(xiàn)代最先進(jìn)的電腦，要窮舉所有的可能性，也無法在我們的有生之年看到結(jié)果。因?yàn)樗枰臅r(shí)間實(shí)在太長了。
那么有沒有一個(gè)像一筆畫一樣的簡便方法？這個(gè)問題不僅奧數(shù)老師沒有教過，現(xiàn)在所有的數(shù)學(xué)家也都不知道。
它是21世紀(jì)七大數(shù)學(xué)難題之一。如果你能夠找到這樣一個(gè)簡便方法，你就可以獲得一百萬美金的獎(jiǎng)金。如果你能證明這個(gè)方法不存在，同樣可以獲得這一百萬美金。
哈密爾頓問題并不是孤立存在的。這世上，有成千上萬個(gè)問題，雖然看起來不一樣，但在計(jì)算復(fù)雜性這件事情上卻是等價(jià)的。等價(jià)的意思就是說，如果你找到其中一個(gè)問題的簡便方法，那么，這成千上萬的問題，你都找到了一個(gè)簡便方法。所以計(jì)算復(fù)雜性是當(dāng)今理論計(jì)算機(jī)科學(xué)焦點(diǎn)之一。
我們的目標(biāo)就是根據(jù)計(jì)算復(fù)雜性把問題進(jìn)行區(qū)分。
像我自己證明了很多二分定理。二分定理的意思就是：所有在一個(gè)框里可以描述的問題，我要把它完全地區(qū)分出哪些是難的，哪些是不難的。
講完計(jì)算理論與數(shù)學(xué)結(jié)合，我們再來講它與經(jīng)濟(jì)學(xué)的聯(lián)系。
我們舉一個(gè)大家比較容易理解的例子——淘寶。
在淘寶中，你輸入一個(gè)關(guān)鍵詞，它會推薦一些商品和商家。
從淘寶的角度來說，它希望為用戶提供最好的體驗(yàn)，所以會盡量把它認(rèn)為優(yōu)質(zhì)的商品與商家推薦給你。那如何評價(jià)商品與商家呢？淘寶用了一系列參數(shù)，比如商家的歷史銷量、用戶評價(jià)等等，然后根據(jù)這些參數(shù)進(jìn)行排名。
排名對每一個(gè)商家來說很重要。如果被排在在前面的話，商品被購買的可能性就會大很多。
所以，很多商家就會用虛假交易的方式來刷銷量、刷評價(jià)，讓自己排名靠前。
如果很多商家都這樣做，用戶的體驗(yàn)就不好了。從計(jì)算的視角來看，淘寶運(yùn)行一個(gè)算法，希望給用戶好的體驗(yàn)。但是因?yàn)檫@些數(shù)據(jù)的生產(chǎn)者是商家，而商家又有各自的利益。它的利益是希望自己的收益最好，而不是希望整體用戶的體驗(yàn)最好。
就在這樣的過程中，算法有其限制性。也就是說，輸入的數(shù)據(jù)并不是完全可控的。這時(shí)候，計(jì)算的極限的分界點(diǎn)其實(shí)就發(fā)生了變化。
為了解釋得更具體，舉一個(gè)我自己科研中的例子。這是一個(gè)最優(yōu)拍賣機(jī)制的設(shè)計(jì)。
大家可能都知道拍賣。大到開發(fā)商拍地，小到在淘寶網(wǎng)上拍賣，甚至大家常說的搜索引擎關(guān)鍵詞的競價(jià)排名，都是用的拍賣方式。
拍賣是經(jīng)濟(jì)學(xué)中非常重要的一個(gè)行為，也有很多關(guān)于設(shè)置最優(yōu)拍賣機(jī)制的研究。但經(jīng)濟(jì)學(xué)的研究一般都基于這樣的假設(shè)：拍賣者知道大家對拍賣品的估價(jià)大概是處在什么樣的分布水平。
這種情況在互聯(lián)網(wǎng)時(shí)代變得越來越不現(xiàn)實(shí)。因?yàn)榛ヂ?lián)網(wǎng)上賣的很多東西，比如競價(jià)排名，你是不可能對每一個(gè)網(wǎng)友做市場調(diào)查的。
所以原來的經(jīng)濟(jì)學(xué)理論很難在現(xiàn)實(shí)中適用。為了改變這個(gè)問題，理論計(jì)算機(jī)科學(xué)家在2001年基于競爭比的概念，提出了新的最優(yōu)拍賣機(jī)制模型。它概念是說，如果競爭比的數(shù)值越小，拍賣機(jī)制期望的收益就會越好。因此對于賣家來說，競爭比越小越好。
而2001年提出的最優(yōu)拍賣機(jī)制，它的競爭比非常大的，是一個(gè)大于100的常數(shù)。之后有好多不同的經(jīng)濟(jì)學(xué)家、數(shù)學(xué)家、計(jì)算機(jī)科學(xué)家試圖設(shè)計(jì)更好的機(jī)制來改進(jìn)這個(gè)競爭比。之前改進(jìn)到最好的是3.12。
這個(gè)改進(jìn)是不是無止盡的？有沒有一個(gè)極限呢？2004年，有科學(xué)家證明這個(gè)數(shù)不能變得比2.42還小。但是，從3.12到2.42怎么做到不知道。
于是，我和我的兩個(gè)合作者一起證明了，存在一個(gè)拍賣機(jī)制，競爭比就是2.42。那么，這就是一個(gè)最優(yōu)的拍賣機(jī)制。
淘寶的排名與拍賣機(jī)制的設(shè)計(jì)催生一個(gè)新的學(xué)科——計(jì)算經(jīng)濟(jì)學(xué)。
這個(gè)學(xué)科包含的領(lǐng)域其實(shí)非常廣，包括像市場價(jià)格的預(yù)測、市場平衡的計(jì)算等等問題。這些問題原來在經(jīng)濟(jì)學(xué)中也有很多研究，但當(dāng)市場越來越大的時(shí)候，關(guān)于計(jì)算的復(fù)雜性成為新經(jīng)濟(jì)學(xué)中的一個(gè)新的約束。
我們講到了計(jì)算理論與數(shù)學(xué)、科學(xué)、經(jīng)濟(jì)學(xué)、技術(shù)的關(guān)系?？梢钥吹剑?/p>
計(jì)算理論與數(shù)學(xué)的結(jié)合體現(xiàn)了理論的深刻性；
在與科學(xué)的結(jié)合中，我們發(fā)現(xiàn)關(guān)于計(jì)算的概念真的出現(xiàn)在物理的世界中，并且影響著宇宙運(yùn)行的規(guī)律，所以是真實(shí)的；
它與經(jīng)濟(jì)學(xué)的結(jié)合，可以看到它的普適性；
而當(dāng)我們看到以計(jì)算機(jī)科學(xué)為基礎(chǔ)的信息科技，正以前所未有的程度改變著我們整個(gè)生活和生產(chǎn)的方式時(shí)，再一次證明了這些計(jì)算工具的有用性。
深刻、真實(shí)、普適、有用，這就是我眼中的計(jì)算思維和計(jì)算原理，也是我十幾年來一直醉心于這個(gè)學(xué)科的原因。
我相信通過計(jì)算的視角，我們可以更好地理解這個(gè)世界；通過計(jì)算這個(gè)工具，我們也可以去更好地改造我們的世界，創(chuàng)造更加美好的未來。
造就：劇院式的線下演講平臺，發(fā)現(xiàn)最有創(chuàng)造力的思想
編輯丨漢嵐
校對丨其奇
