我的研究方向是理论计算机。每次我跟别人说自己的专业时，大家都会问我一个问题：你是做硬件还是软件？
我每次都非常尴尬。因为我既不是做硬件的，也不是做软件的。大学毕业后十几年，我就没有写过程序。我们日常的工作，只要一张纸、一只笔就可以了。
理论计算机的关键词不在计算机，而在计算。我们关注的是计算的理论。
大家可能前两年看过一个电影，叫《模仿游戏》。电影就是以计算理论的祖师爷——图灵的生平作为原型。
图灵在1936年的一篇论文中精确地定义了什么叫计算。这样的精确定义有什么意义呢？
一方面，从他原始的初衷来说，有了这样精确的定义，就可以证明什么东西是不能计算的。
另外一方面的意义可能对我们的影响更大。现代计算机就是在图灵机这样的数学模型基础上造出来的。虽然计算机已经被发明出来了，但计算的理论还是沿着自身的逻辑发展，继续研究计算的真相。
什么是计算的真相呢？
简单来说，就是我们计算的能力到了什么程度？计算的极限又在哪里？什么是可以计算的？什么是不能计算的？什么是容易计算的？什么是不容易计算的？
https://mmbiz.qpic.cn/mmbiz_png/ ... w0Gw/640?wx_fmt=png) 40 25 fill; background-color: rgb(204, 204, 204); box-sizing: border-box !important;">
计算其实是无处不在的。从最深刻最基础的数学到最酷最炫的信息科技应用；从最客观的自然科学，到我们日常生活中的社会、经济行为。计算与它们都有着非常广泛而本质的联系。
非常幸运，我本人的研究方向恰好与数学、科学、技术、经济学这四个纬度都有交叉。所以，我的朋友和合作者中既有数学家、物理学家、经济学家、也有计算机应用科学的学者以及一线的程序员和工程师们。
其实这四类人是非常不一样的，他们之间使用的语言和关注的东西都很不一样，彼此很难对话。但是，他们跟我都对话得很好，合作得很好。我觉得这也从一个角度论证了计算思维的普适性。
在计算与数学、科学、技术、经济学这四个方向的联系中，大家对计算与科学、技术的联系相对好理解一些。
比如它与科学方面的联系。现在最火的技术叫量子信息与量子计算，就是计算与物理学的结合。现在这个领域特别火。不仅各国政府投入了很多资金，很多高科技企业也加入了。就在最近这短短的一年左右，BAT先后成立了量子计算与量子信息的实验室。
计算与技术的结合就更不用说了。现在的高科技都是以计算机科学的技术为基本支撑的。包括大家说得特别多的人工智能技术、区块链技术等等。
不过我今天最想讲的，是计算与数学、经济学的联系。
https://mmbiz.qpic.cn/mmbiz_png/ ... w0Gw/640?wx_fmt=png) 40 25 fill; background-color: rgb(204, 204, 204); box-sizing: border-box !important;">
让我们从数学开始。德国伟大的数学家希尔伯特有一个很重要的贡献。他在1900年巴黎国际数学家大会上，提出了23个数学问题。这23个问题涉及数学非常多不同的方向，很大程度上引导了整个21世纪数学的发展。
后来很多人试图解答他的这23个问题，从而发展出了很多新的数学理论和工具。其中有一些到现在还没有解出来。
我们今天要讲的是他的第10个问题。第10个问题，大家非常好理解，尤其对小时候学过奥数或者有孩子在学奥数的人来说，很好理解。
就是随便给你一个方程，让你回答这个方程有没有整数解？（编者按：即不定方程可解性）
前段时间，有个特殊的方程在我的朋友圈里刷屏了。
这个方程看起来非常简洁，也没有什么特殊的。问题是存不存在三个正整数ABC使得这个方程成立。
这题为什么很有趣呢？
因为这样的正整数确实是存在的，但如果你去算一下的话，我相信你不会很快算出来。因为它最小的一个正整数解是长这个样子的。具体多少位我也没数过。
从这个例子，大家可以看出。不是所有的问题都可以通过输入方程，就能把解给找出来。
就像希尔伯特第10问题，虽然已经有了答案，但结果却不是希尔伯特所希望的。希尔伯特希望找出一个通用的方法。但我们通过计算理论证明了通用方法是不存在的。不存在一个算法，可以给你一个方程，就能确定地找到一个解。
这样一种否定性的回答，有时候在数学中反而具有更加深刻的意义。
计算的理论现在已经发展得很成熟了。我们大家已经知道，哪些问题是可以算的，哪些问题是不能算的。
现在，计算理论关注的焦点已经从能不能算发展到了难不难算。也就是计算的复杂性问题。
计算复杂性怎么理解？意思是我们要用多长时间来把这个问题给算出来。
我们再举一个奥赛题。这是一张纸，上面有一张图。你沿着图上的线画，但是同一条线不能画两次，你能不能把这个图一笔画出来？
如果尝试所有的画法，需要很久；如果这个图再大一点，就更麻烦了。有没有一个简便的方法呢？
我想很多人会知道这个简便的方法。那就是你看每一个点连接的线是奇数条还是偶数条。偶数条我们就叫偶点，奇数条叫奇点。如果一个图的奇点数不超过2的话，这个图就是可以一笔画的。
有了这样一个简单的辨别方法，即使这个图里有几百个点，你也能很快判断出能不能一笔画完。
如果我把这个题稍微换一下，说图中的每个点都不能重复呢？就好比这是一个游览图，每个点代表一个景点，你能不能把所有的景点没有重复地游览一遍？
这个问题在数学上称为哈密尔顿道路问题。当然你可以把所有可能的路线图都走一遍。但如果这个图的点数超过几百的话，即使用现代最先进的电脑，要穷举所有的可能性，也无法在我们的有生之年看到结果。因为所需要的时间实在太长了。
那么有没有一个像一笔画一样的简便方法？这个问题不仅奥数老师没有教过，现在所有的数学家也都不知道。
它是21世纪七大数学难题之一。如果你能够找到这样一个简便方法，你就可以获得一百万美金的奖金。如果你能证明这个方法不存在，同样可以获得这一百万美金。
哈密尔顿问题并不是孤立存在的。这世上，有成千上万个问题，虽然看起来不一样，但在计算复杂性这件事情上却是等价的。等价的意思就是说，如果你找到其中一个问题的简便方法，那么，这成千上万的问题，你都找到了一个简便方法。所以计算复杂性是当今理论计算机科学焦点之一。
我们的目标就是根据计算复杂性把问题进行区分。
像我自己证明了很多二分定理。二分定理的意思就是：所有在一个框里可以描述的问题，我要把它完全地区分出哪些是难的，哪些是不难的。
https://mmbiz.qpic.cn/mmbiz_png/ ... w0Gw/640?wx_fmt=png) 40 25 fill; background-color: rgb(204, 204, 204); box-sizing: border-box !important;">
讲完计算理论与数学结合，我们再来讲它与经济学的联系。
我们举一个大家比较容易理解的例子——淘宝。
在淘宝中，你输入一个关键词，它会推荐一些商品和商家。
从淘宝的角度来说，它希望为用户提供最好的体验，所以会尽量把它认为优质的商品与商家推荐给你。那如何评价商品与商家呢？淘宝用了一系列参数，比如商家的历史销量、用户评价等等，然后根据这些参数进行排名。
排名对每一个商家来说很重要。如果被排在在前面的话，商品被购买的可能性就会大很多。
所以，很多商家就会用虚假交易的方式来刷销量、刷评价，让自己排名靠前。
如果很多商家都这样做，用户的体验就不好了。从计算的视角来看，淘宝运行一个算法，希望给用户好的体验。但是因为这些数据的生产者是商家，而商家又有各自的利益。它的利益是希望自己的收益最好，而不是希望整体用户的体验最好。
就在这样的过程中，算法有其限制性。也就是说，输入的数据并不是完全可控的。这时候，计算的极限的分界点其实就发生了变化。
为了解释得更具体，举一个我自己科研中的例子。这是一个最优拍卖机制的设计。
大家可能都知道拍卖。大到开发商拍地，小到在淘宝网上拍卖，甚至大家常说的搜索引擎关键词的竞价排名，都是用的拍卖方式。
拍卖是经济学中非常重要的一个行为，也有很多关于设置最优拍卖机制的研究。但经济学的研究一般都基于这样的假设：拍卖者知道大家对拍卖品的估价大概是处在什么样的分布水平。
这种情况在互联网时代变得越来越不现实。因为互联网上卖的很多东西，比如竞价排名，你是不可能对每一个网友做市场调查的。
所以原来的经济学理论很难在现实中适用。为了改变这个问题，理论计算机科学家在2001年基于竞争比的概念，提出了新的最优拍卖机制模型。它概念是说，如果竞争比的数值越小，拍卖机制期望的收益就会越好。因此对于卖家来说，竞争比越小越好。
而2001年提出的最优拍卖机制，它的竞争比非常大的，是一个大于100的常数。之后有好多不同的经济学家、数学家、计算机科学家试图设计更好的机制来改进这个竞争比。之前改进到最好的是3.12。
这个改进是不是无止尽的？有没有一个极限呢？2004年，有科学家证明这个数不能变得比2.42还小。但是，从3.12到2.42怎么做到不知道。
于是，我和我的两个合作者一起证明了，存在一个拍卖机制，竞争比就是2.42。那么，这就是一个最优的拍卖机制。
淘宝的排名与拍卖机制的设计催生一个新的学科——计算经济学。
这个学科包含的领域其实非常广，包括像市场价格的预测、市场平衡的计算等等问题。这些问题原来在经济学中也有很多研究，但当市场越来越大的时候，关于计算的复杂性成为新经济学中的一个新的约束。
https://mmbiz.qpic.cn/mmbiz_png/ ... w0Gw/640?wx_fmt=png) 40 25 fill; background-color: rgb(204, 204, 204); box-sizing: border-box !important;">
我们讲到了计算理论与数学、科学、经济学、技术的关系。可以看到：
深刻、真实、普适、有用，这就是我眼中的计算思维和计算原理，也是我十几年来一直醉心于这个学科的原因。
我相信通过计算的视角，我们可以更好地理解这个世界；通过计算这个工具，我们也可以去更好地改造我们的世界，创造更加美好的未来。
狗仔卡
发表于 2018-4-17 08:55 PM
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡