莱昂纳德·莱维（Leonid Levin），也译为利奥尼德·莱文，美国波士顿大学著名数学家。
Leonid Levin在1973年发表了一个以搜寻问题为基本而类似於Cook的结果，据Levin自己的陈述，他在1971年即已经得到此结果，目前有时我们称该定理为Cook-Levin定理。即是否两个复杂度类P和NP是恒等的（P=NP?）。
基本资料编辑本段回目录
Leonid Anatolievich Levin
Born November 2, 1948 (1948-11-02) (age 61)
Dnipropetrovsk, Ukraine
Fields Computer Science
Institutions Boston University
Alma mater Moscow University
Doctoral advisor Andrey Kolmogorov, Albert R. Meyer
Known for research in complexity, randomness, information
简介编辑本段回目录
Leonid Anatolievich Levin (Russian: Леонид Анатольевич Левин; Phonetic: Le-oh-NEED Le-vin; born November 2, 1948 in Dnipropetrovsk Ukrainian SSR) is a Russian-American computer scientist.
He obtained his master degree in 1970 and a Ph.D. equivalent in 1972 at Moscow University where he studied under Andrey Kolmogorov. Later, he emigrated to the U.S. in 1978 and also earned a Ph.D. at the Massachusetts Institute of Technology (MIT) in 1979. His advisor at MIT was Albert R. Meyer.
He is well known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory.
His life is described in a chapter of the book Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists.
Levin independently discovered a theorem also proven by Stephen Cook. This NP-completeness theorem, often called the Cook-Levin Theorem, was a basis for one of the seven "Millennium Math. Problems" declared by Clay Mathematics Institute with a $1,000,000 prize offered. It was a breakthrough in computer science and is the foundation of computational complexity. Levin's journal article on this theorem was published in 1973; he had lectured on the ideas in it for some years before that time (see Trakhtenbrot's survey)[3], though complete formal writing of the results took place after Cook's publication.
He is currently a professor of computer science at Boston University, where he began teaching in 1980.
千禧年数学问题编辑本段回目录
克雷是波士顿地区很有名的一个商人，毕业于哈佛大学英语系，做的是风险投资生意，上过《福布斯》富人榜。1998年，他以自己和夫人拉维尼娅·克雷的名义，在哈佛大学所在地坎布里奇投资创办了克雷数学研究所（Clay Mathematics Institute）。2000年5月24日，在法国巴黎法兰西学院举办的一次学术会议上，还不甚为人所知的克雷数学研究所给自己打了一个“漂亮的广告”——丘成桐语。作为对100年前希尔伯特23个数学问题的响应，克雷数学研究所董事会宣布，设立700万美元的大奖，征集对7个著名数学难题的解决方案。
同各自艰深且难以用短短几句话介绍清楚的数学猜想和方程相比，“千禧年数学问题”（Millennium Prize Problems）这个概念无疑对公众更具亲和力，而每个问题100万美元的悬赏，又成了“书中自有黄金屋”的最佳注脚。结果可想而知:在Google上搜索“Millennium Prize Problems”，得到的结果有187万条，继续搜索其中之一的庞加莱猜想“Poincare conjecture”，仅有39.7万条。而这，还要拜近几年中庞加莱猜想有望解决而引起的公众关注所赐。
7个千禧年数学问题，分别是：1：1971年斯蒂芬·库克（Stephen Cook）和莱昂纳德·莱维（Leonid Levin）各自独立提出的“P与NP问题”，2、19世纪德国数学家黎曼（G.Riemann）提出的“黎曼假设”，3、1904年法国数学家亨利·庞加莱提出的“庞加莱猜想”，4、英国数学家威廉·霍奇（William Hodge）在上世纪30年代提出的“霍奇猜想”，5、60年代彼得·斯温纳顿·戴尔和布赖恩·伯斯提出的伯斯－斯温纳顿·戴尔猜想，6、物理学家克劳德-路易斯·尼维亚和乔治·斯托克斯提出的一系列关于流体力学问题的尼维亚-斯托克斯方程组，7、杨振宁和罗伯特·米尔斯关于量子场问题的杨－米尔斯理论。
附：
庞加莱猜想：据说已经破解 （破解人为中国数学家朱熹平和曹怀东）
黎曼假设：很多人攻关，没看到希望
霍奇猜想：进展不大
杨-米尔理论：太难，几乎没人做
P与NP问题：没什么进展
波奇和斯温纳顿戴雅猜想：有希望破解
纳威厄-斯托克斯方程：离解决相差很远
NP问题编辑本段回目录
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。
P和NP
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:
P和NP相等吗?
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。[1] 对于正确的解答，有一个1,000,000美元的奖励。
NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。
假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如，我们可能问53308290611是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。验证一个数是除数比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证书。所以我们的结论是，给定 正确的证书，问题的正面答案可以很快的(也就是，在多项式时间内)验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，最近被证明为也在P类中(参看下面的关于"质数在P中"的参考),这一点也不明显，而且有很多类似的问题相信不属于类P。
限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题(是否FP = FNP)是等价的。
形式化定义
更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如图灵机，或一个LISP或Pascal的程序并有无限的内存）能够在最多nk步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在多项式时间内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。
现在假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多nk步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）。进一步假设
w是一个答案为“是”的例子，当且仅当，存在C使得A(w,C)返回“是”。
则我们称这个问题可以在非决定性多项式时间内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（多项式）”而不是代表“Non-Polynomial（非多项式）。）
NP完全
要解决P = NP问题，NP完全的概念非常有用。不严格的讲，NP完全问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行商问题的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。
更难的问题
虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是指数时间完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比多项式时间更多的时间。判定Presburger算术中的命题是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少2^(2^(cn))的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如停机问题。它们无法在任何给定时间内解决。
P真的容易处理吗？
上面所有的讨论假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是线性时间的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是指数时间的），但是对于n 取值直到几千时还是很容易处理的。
它忽略了指数的大小。一个时间复杂度n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间等级定理）。一个时间复杂度2n/1000的问题不属于P，但对与n直到几千还是容易应对的。
它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP， BPP）。
新的诸如量子电脑这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用象图灵机这样的经典计算模型的属于表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
计算机科学家为什么认为P ≠ NP？
多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 余NP和P = PH。
也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的。
从另一方面讲，某些研究者认为我们过于相信P ≠ NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明：
倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ] 费马最後定理的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。
— Moshe Vardi，莱斯大学
过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。
— Anil Nerode, 康奈尔大学
关于证明的难度的结果
虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些形式化的结果证明为什么该问题可能很难解决。
最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。[3] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。
这实际上也是为什么NP完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法，对于NP完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决P = NP问题。
多项式时间算法
没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当P = NP。
// 接受NP完全语言的一个算法子集和。
//
// 这是一个多项式时间算法当且仅当P=NP。
//
// “多项式时间”表示它在多项式时间内返回“是”，若
// 结果是“是”，否则永远运行。
//
// 输入：S = 一个自然数的有限集
// 输出："是" 如果某个S的子集加起来等于0。
// 否则，它永远运行没有输出。
// 注意: "程序数P" 是你将一个整数P写为二进制，然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生，
// 虽然多数什么也不做因为有语法错误。
//
FOR N = 1...infinity
FOR P = 1...N
以S为输入运行程序数P N步
IF 程序输出一个不同的整数的列表
AND 所有整数都在S中
AND 整数的和为0
THEN
OUTPUT "是" 并 停机
若P = NP，则这是一个接受一个NP完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
IF 程序输出一个完整的数学证明
AND 证明的每一步合法
AND 结论是S确实有（或者没有）一个和为0的子集
THEN
OUTPUT "是" （或者"不是"如果那被证明了）并停机
逻辑表述
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用一阶逻辑加上最小不动点操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性二阶逻辑来表达—也就是，在关系、函数、和子集上排除了全域量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”
花絮
普林斯顿大学计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[4]
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。
Levin悖论：联合起来，变得虚弱编辑本段回目录
不要怪我犯哗众取宠的毛病，这个题目不是我取的，这是法国著名的数学科普作家Jean-Paul Delahaye在2001年12月号《为了科学》，即《科学美国人》的法文版上发表的一篇文章的题目。我觉得这文章很有意思，觉得很可以介绍给大家；同时也是表达对一位离网隐去不少时候的朋友的怀念，他和我打过一个赌，而这篇文章，就是谈打赌问题的。
在9月号的《为了科学》中，Delahay提出了一个奇怪的问题，并表示他自己也不太清楚毛病出在了什么地方，希望有兴趣的读者能帮助他找到一个令人满意的答案。要理解他提出的问题，首先让我们来看一些基本概念。
如果有人要和你打赌，比如说抛六面的骰子（当然我们要规定这个骰子没被灌了某种液体或者有其他的猫腻，我们毕竟是讨论数学问题，不是真要学好本领去赌博甚至出老千，下面所有的情况都不这么一一说明了）。如果他建议，抛出1来，他就给你3元，抛出2或3来，你就给他1元，而其他情况大家不输不赢。那么这个赌你应不应该打呢？很显然，如果这样的赌多进行几次，那么平均说来，在六次里有一次抛出1，有两次抛出2或3，有三次抛出其他的数字。所以平均说来，在六次里你会赢一次3元，输两次1元，于是总的来说你会赢3-2*1=1元，也就是说平均每次你会赢1/6元。当然偶然某次你会抛到2或3，输掉1元，但是从长远的角度来看，你会不断地赢钱。所以你应该接受这样的赌局。
在数学上，上面的1/6元被称作这种赌局对你来说的期望，就是把每种可能发生的情况的概率和在此情况下你赢的钱的数目（如果是输，那么钱为负）乘起来，再把从所有这些情况下计算出的值加起来。一般来说，期望是正的，赌局对你就有利，如果是负的，那么就对你不利。而且如果把参加赌局的所有人的期望都加起来，一定是0，因为总体看起来，在赌博中钱从一个人那里跑另一个人那里去了，但是不会凭空多出来或少掉。比如上面那个向你建议赌博的人，他的期望就是-1/6元，平均一次他会输掉这么多，所以他其实不该向你建议这次赌博的。
现在假设在向你建议以上的赌局的同时，此人还向你建议另一个赌局：如果抛出2，你就赢2元，如果抛出4，你就输1元，其他情况大家不赢不输。同样的算法，你会发现这种赌法对你也有利——你的期望是2*1/6-1*1/6=1/6元。如果把上面的赌局和这个赌局同时玩（也就是说只抛一次骰子，但是两个赌局都按这次抛骰子的结果来结算输赢），那么结果如何呢？如果抛出1，那么按第一个赌局你赢3元，按第二赌局大家不赢不输；如果抛出2，那么按第一个赌局你输1元，按第二赌局你赢2元，总体说来你赢1元；同样地，总体说来，抛3，你输2元，其他情况大家不赢不输。所以如果两局同时赌，你的期望就是3*1/6 +1*1/6-2*1/6=1/3元。
我们把这样多局同时赌的赌法称为“复式赌局”。比如说在现实生活中你去买张复式彩票，甚至包局，这就是一种复式赌局。我们可以证明，复式赌局的期望就是里面每个单局赌局的期望之和，比如上面的复式赌局的期望就是1/6+1/6=1/3元。所以如果一个复式赌局里每一局都对你有利，也就是期望都是正的，那么整个复式赌局的期望当然也就是正的，对你有利，如果有人向你建议这么个赌局，就该毫不犹豫地接受。这可以被称作“复式原则”。
一、Levin悖论
可是且慢。数学家Leonid Levin在2001年的《数学报道员》第23期上提出了一个奇怪的悖论，似乎和“复式原则”相抵触，虽然每一个的赌局对你都有利，可是如果你同时接受所有的赌局，你就一定会输！
为了把他的例子说清楚，我们需要一点实数理论的知识（如果看不懂这个例子，你可以看后面的例子，后面的例子比较容易看懂）。考虑所有的实数。有些实数在十进制表示下小数部分的位数是有限的，比如1.2568，-9.5555等（虽然上面的两个小数也可以写成无限小数的形式，比如1.2568= 1.2657999999……，但是我们规定如果循环节为9，那么一律写成有限小数的样子，这样每个实数都只有唯一一种表示），也有一些小数部分的位数是无限的，比如1/3表示成十进制小数就是0.3333……，或者π=3.14159……。
我们可以把实数分成一组一组的，两个实数在同一组，当且仅当它们的差是有限小数。比方说，所有的有限小数自然都在同一个组里；π、π+0.25、π-100也都在同一个组里（当然这个组里不止这么几个数）。很显然，一个实数x只能在一个组里，如果它同时在两个组里，我们从第一组里拿一个不在第二组里的a，又从第二组里拿一个不在第一组里的b，那么因为x既在第一组里又在第二组里，所以x-a和x-b都该是有限小数，但是这么一来(x-a)-(x-b)=b-a也该是有限小数，这就和a、b不在同一组里矛盾了。
于是我们就把所有的实数分成了互不相交的一些组（或者说集合），每个实数都在而且仅在一个组里。事实上这样分好的组有无限多个。现在我们从每个组里选一个组长。组长是谁无所谓，只要一个组只有一个组长，而且组长是组里的成员就可以了。有个组长的好处是我可以用组长来称呼这个组，比方说我可以说“π所在的那个组”。也不一定非选π是组长，你完全可以选π+1.2356是组长，那么“π+1.2356所在的那个组”和“π所在的那个组”其实是同一个组。但是要注意的是，组长可以随便选，但是一旦组长选好了，就定下来不能变了，一个组只能有一个组长。
现在假设每个组都选好了组长，我们把所有组长的集合记为C，而把所有有限小数组成的集合记为D（很容易知道，这其实就是一个组）。现在任何一个实数x都可以写成c+ d的形式，这里c是C中一个元素，d是D中的元素。这样的表达方法是唯一的。事实上，任何一个实数x都属于某一组，那么假设这个组的组长是c，x就可以写成c+(x-c)，根据组的定义，x-c属于D。
现在我们可以来谈论赌局了。
随机地选取一个0和1之间的实数（包括 0，不包括1）。这个选法可以是象幸运轮那样的赌法，只是现在不是一格一格地写着数字了，而是轮周上的每一点都是一个不同的选择：拿一个周长为1的圆盘，上面标好一个点算原点，正上方有个不动的指针指着圆周上的某一点。然后让圆盘高速旋转，随机地让它停下来，然后测量原点顺时针方向到现在指针所指的位置的距离，这个距离就是我们随机选取的实数。
从上面的讨论我们知道，这个随机选取的实数可以被唯一地写成c+d的形式，其中c是一个组长，而d是一个有限小数。现在我向你建议我们打一个这样的赌：如果d是0.7，那么你赢2元，如果d是0.9，那么你输1元，其他情况我们都不赢不输。
这个赌自然对你有利，因为那个d是0.9还是0.7的可能性是一样的，但是在一种情况下你只输1元，而另一种情况下你赢2元。事实上如果我们用P(d,d')来表示这样的赌局（这里d和d'是两个不同的有限小数）：
随机选取一个0和1之间的实数x，我们找到它所在的组，组长为c，那么如果x是c+d，你赢2元，如果x是c+d'，你输1元。上面我建议的赌局就是P(0.7,0.9)。和上面同样的分析我们知道，无论是什么d和d'，这个赌局对你来说都是有利的。
现在我来建议一个复式赌局，我们来赌所有这样的P(d,d')的赌局，这里d'是把d的小数部分第一位去掉后的小数。比如说P (0.1234,0.234)，P(0.98521,0.8521)，P(0.321,0.21)都是这个复式赌局里要考虑的赌局。因为每个P(d, d')对你都是有利的，你自然会觉得这么一个复式赌局对你也该有利——可是这完全错了。
假设我们随机选取的实数可以写成c+0.321 的样子，我们来看看你到底会赢多少。你唯一赢的那个赌局是P(0.321,0.21)，你赢了2元。可是你输了P(0.0321,0.321)，所以输了 1元，而且不仅如此，你还输了P(0.1321,0.321)，P(0.2321,0.321)，……P(0.9321,0.321)这些赌局，所以一共输了10元。总体说来，你输了8元。糟糕的是，无论随机选取的实数是什么，你都会这么每次输掉8元！
这怎么可能呢？每个赌局都对你有利，可是要是同时赌这些赌局，你却必输无疑！
二、对Levin悖论的评论，以及对评论的评论
在2001年9月号的《为了科学》上Jean-Paul Delahaye提出了三种对Levin悖论的解释，但是都不很令人满意。
首先是使用选择公理可能带来的问题。选择公理是数学家策梅罗于1904年首先引入的（尽管在此之前它已经无数次地被隐含地使用），它是说，如果给定一组非空的集合（这组集合中集合的数目可以是任意多），总能够从每个集合中挑出一个元素来组成一个新的集合，按上面的说法，就是总能选出一个组长的集合来。很显然，我们上面选取组长时使用了这个公理。虽然已经证明选择公理和集合论其他公理是独立的，也就是说如果没有选择公理的集合论里不存在矛盾，那么加上选择公理（或者选择公理的否命题）的公理系统也不存在矛盾，但是数理逻辑学家对选择公理仍然心有余悸，因为通过它能推导出一些奇怪的命题来，其中最著名的就是巴拿赫-塔斯基定理。这个定理的一个特例说，我们能够把一个球体分割成有限多块，然后重新组织拼合成两个和原来一模一样的球体。这看起来实在是奇怪，不过要知道这样的分割后的块是非常特别的，它们甚至不能被定义体积（所谓的不可测集），所以要通过这样的分割来拼金球发大财是不可能的。
但是尽管选择公理会带来这样奇怪的结论，不过它从来没有引起过真正的自相矛盾。可是上面我们遇见的却是一个真正的矛盾：每局都有利，一起赌却必定失利。
其次是有限情况下的“复式原则”能不能使用到无限的情况下去。我们只是针对有限情况证明了“复式原则”，但是也许在无限情况下这个原则出了错。
但是在有限情况下我们不仅证明了一组有利的赌局的组合仍旧是有利的，而且我们还证明了复合赌局的期望就是每一局赌局的期望的和。在无限情况下形势仍旧相同，如果所有赌局的期望都是正的，那么复合赌局的期望为什么会是负的？这点不能用有限无限来不明不白地推托掉，无论如何要搞搞明白。
最后，是不是连续型的概率分布出了问题？我们看到这里我们需要从0到1的实数中随机选取一个实数，为了知道它所属的组的组长，我们必须知道这个数小数点后所有的位数，这实际上是办不到的。比
方说上面所说的转盘方法，但这需要无限精确地测量指针那一点到原点的距离，这其实是不可能的。
但是在概率统计学家到处在使用这类分布，要是这也有可能带来错误的话，那整个概率统计学就完蛋了，现在的概率统计学家怎么还能这么心定气闲地一篇接一篇地写着关于连续型概率分布的论文。数学毕竟是一门抽象的学科，所以实际办不办得到不能成为拒绝使用连续型概率分布的理由（你在现实中看见过一条没有宽度的直线，或者一个无穷集合吗？）。相反地，Levin悖论给我们一个启示，就是把数学中的知识应用到实际中去时，我们应该保持警惕。
三、构造新的悖论
很明显，上面的这些解释都只能让我们受惊的心灵得到暂时的安慰，但是问题仍旧在那里。要么我们把脑袋藏在沙子里，满足于这些简单肤浅的托词，要么我们必须更仔细地分析问题到底出在了哪里。为此我们必须简化Levin悖论，把不是引起悖论的根本原因的细枝末节丢开。
选择公理的毛病出在它只告诉在我们那个组长的集合C存在，却不能具体地构造它。但是这并非由于我们对它的了解不多而造成的，事实上，由选择公理和集合论其他部分的独立性，数学家可以证明这个集合C是不可能被具体构造的构造它（也就是具体地描述它，使得有一种至少理论上的方法使得任给一个具体的实数，我们就可以通过一系列计算来确定它是否属于C）。
但是选择公理在Levin悖论中所起的作用只是伪装性的，《为了科学》的一位读者Jacques Patarin提出了一个新的类似于Levin悖论的悖论，它不使用选择公理。
Patarin悖论是这样的：对于每个0到1之间的实数x，我们定义赌局P(x)为：
1. 随机选取一个0到1之间的实数y（每个实数选到的可能性相同，即概率论中的平均分布）；
2. 如果y=3/4x，那么我输1元；
3. 如果y=3/4+x/8或者y=7/8+x/8，那么我赢1元；
4. 如果y是其他数，则不赢不输。
对每个x来说赌局P(x)对我都是有利的。和每个赌局有关系的是三个点：3/4x、3/4+x/8和7/8+x/8，每个点被选中的可能性都一样，但是其中有两个点我会赢钱，但是只有一个点会让我输钱。
但是想像一下如果我们接受对所有的0到1之间的实数x（包括0，不包括1）的赌局P(x)，会发生什么事。
如果随机选取的y>3/4，那么我什么赌局都不会输，因为此时不会有一个0到1之间的实数x使得y=3/4x，但是我会赢得赌局P(8(y- 3/4))和P(8(y-7/8))。如果随机选取的y<3/4，那么我不可能赢得任何赌局，但是我会输掉赌局P(4/3y)。问题在于平均四次里只有一次y会大于3/4，让我赢2元，而会有三次y小于3/4，让我总共输3元。于是平均起来我每四次平均会输掉1元！
Patarin悖论中就完全不牵涉到选择公理了。不过它的其他毛病和Levin悖论相同，大家仍旧可以说，随机地选取一个0到1之间的数字是不能实际操作的，或者有限情况得到的结论不能随便使用到无限情况下去。特别地，它使我们似乎找到了一个新理由：零概率事件。
注意到在Levin悖论和Patarin悖论中，每个单独的赌局中有输赢的事件发生的概率都是0，比如说Patarin悖论中如果我们只赌赌局P (1/2)，那么在y=3/8时我会输，而在y=13/16或15/16时我会赢。但是这三点被选到的可能性都是0，所以即使这个赌局实际能进行的话，大家都会不赢不输。
这个解释虽然仍旧让人感到不舒服，但是“一组不赢不输的赌局合起来会变成会输的赌局”总比“一组会赢的赌局合起来会变成会输的赌局”听起来另人心安一些。看样子这些悖论的问题出在对零概率事件的滥用上。
但是真的如此吗？
四、终极例子，Monnier悖论
对于Levin悖论和Patarin悖论，我们已经用选择公理，和滥用零概率事件把它们造成的矛盾都推脱掉了，也就是说，我们因为这些事情在现实中是不能发生的这样的“实际”理由，来解释理论上的矛盾。这看起来无论如何都象鸵鸟的作为，特别是，现在有人举出了一个实际上可以办到的例子。
Samuel Monnier发明了这样一个赌局。首先赌博的方法是用抛硬币的方法来随机选取一个自然数：接连不断地抛一枚均匀的硬币（就是说得到正面朝上和反面朝上的可能性都是1/2），如果第一次就是正面，那么这个自然数就是1；如果第一次结果是反面，那么继续抛硬币，如果第二次的结果是正面，那么这个自然数就是 2；如果第二次结果是反面，那么继续抛硬币……总而言之，如果抛到了反面就继续抛，如果抛到了正面，就把抛硬币的次数记为结果n。
我们很容易就知道，用这样选择自然数的方法，得到1的可能性是1/2，得到2的可能性是1/4，……，得到n的可能性是1/2n。
现在有以下的赌局：
赌局P(1)，如果得到的数是1，那么你输1元；如果是2，那么你赢3元；如果是其他数，就不输不赢。
赌局P(2)，如果得到的数是2，那么你输4元；如果是3，那么你赢9元；如果是其他数，就不输不赢。
赌局P(3)，如果得到的数是3，那么你输10元；如果是4，那么你赢27元；如果是其他数，就不输不赢。
……
赌局P(n)，如果得到的数是n，那么你输3n-1+1元；如果是n+1，那么你赢3n元；如果是其他数，就不输不赢。（n＞1）
……
很明显，这里每个赌局是可以实际执行的，而且赢和输都不是零概率事件。而且每个赌局对你来说都是有利的。比如说第n个赌局：我们知道抛到n的可能性是 1/2n，而抛到n+1的可能性是1/2n+1，所以这个赌局你赢的期望是-(3^(n-1)+1)*1/2^n+3^n*1/2^(n+1)=(3^n -2*(3^(n-1)+1))/2^(n+1)=(3^(n-1)-2)/2^(n+1)元
但是当n＞1时，3^n＞2*(3^(n-1)+1)，所以这个期望一定是正的。
但是如果你把所有这些对你有利的赌局一起接受了，会怎么样呢？如果抛硬币得到的结果是1，那么你什么赌局都没赢，却输了赌局P(1)，输1元钱；如果抛硬币得到的结果是2，那么你赢了赌局P(1)，得到3元，却输了赌局P(2)，输4元钱，总的来说输1元；……；如果抛硬币得到的结果是n，那么你赢了赌局P(n-1)，得到3n元，却输了赌局P(n)，输3n+1元钱，总的来说输1元；……于是，无论抛出什么数来，你每次都会输掉1元！
这个排除了选择公理，零概率事件的“纯化”Levin悖论非常令人吃惊，通过这个终极例子，我们终于发现了造成这种“联合起来，变得虚弱”悖论的根本原因。
五、加法的结果……不仅取决于加式中的数，也取决于数的顺序！
在第二节中我们谈到过Levin悖论的可能原因，其中第二条的理由是，“所以如果一个复式赌局里每一局都对你有利，那么整个复式赌局对你有利”这条“复式原则”对于有无限个赌局的复式赌局很可能是不成立的，正是此理！在第二节中我们还不清楚为什么，而由于Monnier悖论，我们将其原因看得一清二楚。
如果我们构造一个矩阵，把Monnier悖论中的每个赌局作为纵坐标，而把抛得的结果作为横坐标，在相应位置填入在此赌局中抛到此结果赢得（或输去）的钱数乘以抛得此结果的概率：
我们发现，这个矩阵的特点是，如果先把每行的数值加起来（就是先计算每局的期望），那么每个数都是正的，但是如果先把每列的数值加起来，数值却是负的！当我们只接受某一个赌局时，每局平均赢的钱，就是表示该赌局的那一行的期望，它等于把此行的所有数加起来的值，这个值是正的，所以这一局对我们有利。但是如果我们接受了所有赌局，我们首先要计算的是抛到某个数字时我们能赢的钱，这个数值是把上面矩阵中的值先按列加，再除以抛到这个数值的概率，于是它就是负的！正是这种奇怪的矩阵，使我们陷入了“每个赌局都有利，可是接受所有的赌局就输钱”的困境。
在计算无穷和时，我们一定要注意到这一点，如果在被加起来的项中，有无穷多的项是正的，也有无穷多的项是负的，那么这个无穷和的结果不仅仅取决于加式中的数，也取决于这些数在加式中的顺序。就象上面这个矩阵所说明的，如果我们先按行加，那么所得结果是正的，如果先按列加，所得结果就是负的，虽然参加加法的都是同一个矩阵中的数。不仅对于矩阵中的数的和，对一般的级数也是如此。牛顿时代的数学家们已经开始注意到对于象1-1+1-1+1-1+……这样的我们现在称为发散级数的无穷和，如果计算加法的次序不同，就会有不同的结果：(1-1)+(1-1)+(1-1)+……=0; 1-((1-1)+(1-1)+(1-1)+……)=1; 事实上，对于象1-1/2+1/3-1/4+1/5-……这样的级数，数学分析中有定理保证，任意给定一个实数，我们必定能够重新组织这个级数中加法的顺序（加式中的数字仍旧是1，-1/2，1/3，……等等，一个不多，一个不少），使得最后级数的和为此实数。换句话说，数字仍旧是那些数字，只要适当地换一换加起来的顺序，我们可以爱得到什么结果就得到什么结果。
Levin悖论和Patarin悖论同样也是由此原因引起，只是此时的矩阵的行与列的数目都为不可数无穷多，它们各自对应的矩阵也具有同样的特点：当按行相加时，每行的结果都是正数，可是按列相加时，每列的结果却是负数。
一旦我们搞清了这一点，就可以创造出无数和Monnier悖论类似的悖论来——只要找到一个合适的矩阵就可以了。
最简单的“每行加起来为正，每列加起来为负”的矩阵可能是下面这一个：
如果考虑到每一列上的1/2n概率因子，把上面的矩阵写成以下形式，我们就得到了一个类似于Monnier矩阵的关于某个赌局的矩阵：
从中我们推出这个赌局是这样的（抛硬币得到数字的方法同Monnier悖论）：
P(1)：如果抛出1，输2元；如果抛出2，赢8元。
P(2)：如果抛出2，输12元；如果抛出3，赢32元。
……
P(n)：如果抛出n，输(2n-1)2n元；如果抛出n+1，赢2n2n+1元。
每个单独赌局的期望都是1元，但是如果你接受了所有赌局的话，抛出n你就输2n元。
这个赌局被叫作“疯狂会计师”赌局。
下面的“疯狂赌徒”赌局我只给出矩阵，由读者去补充具体的赌局：
注意到这里每个单独赌局的期望都是1元，可是全部接受每次反而要输掉1元。
最后一个例子是很有意思的Ludovic Galant赌局：
P(1)：如果抛出1赢3元，抛出其他数输1元。
P(2)：如果抛出2赢7元，抛出其他数输1元。
P(3)：如果抛出3赢15元，抛出其他数输1元。
……
P(n)：如果抛出n赢2n+1-1元，抛出其他数输1元。
它的矩阵是：
注意到这里每个单独赌局的期望都是1元，可是全部接受每次会输掉无穷的钱！
六、诚实的人有福了
在前面讲到的这些赌局中，我们注意到，当n越大时，P(n)中的输赢数字也越大，当n趋向无穷大时，输赢数字也趋向于无穷大。而一个诚实的人，是不应该进行万一输了，他付不起赌资的赌局的，即便他赢的可能性很大。如果同时接受所有这无穷多个赌局，那么这意味着冒输掉任意大的赌注的危险。所以诚实的人即使想赌博，也只会接受其中有限个赌局。但是如果赌局数目有限的话，正如在本文开头所说，“复式原则”成立，如果每一个赌局都有利，那么同时接受这有限多个赌局也有利。在这里我们发现，和政治家所玩的游戏不同，复式赌局使得诚实反而保护了诚实人的利益……
在本文开头我提到一位离网隐去不少时候的朋友，他是网易广州社区自然科学版原版主云胡不归，在2000年的八月份，我们打过一个赌，赌一位声称证明出了P=NP的江湖数学家是否真证出了这个著名定理。我对这种事情只有亿分之一的信任度，而云胡兄却更干脆，一点都不信。于是我们打个一个一比一亿的赌——如果一年后这个结果被数学界承认了，云胡得给我一亿元，如果一年后这个结果还没有被数学界承认，我要给云胡一元钱。根据上面的讨论，在这个赌博里云胡兄不是个诚实的人——除非他真拿得出一亿元来，不过他似乎不象是个亿万富翁。
咳，最后搞得还是我最不诚实，一年以后，我再也没有听说那个江湖数学家的消息——如果真证出P=NP来，这么大的消息我不至于不知道，而云胡兄已经不见踪影了——所以直到现在我还没有付这输掉的一元钱。
