1700496580
尽管你可能从来没有听说过米勒-拉宾测试，但你的笔记本电脑、平板电脑和手机都对其很熟悉。在其被发现后的几十年，它仍然在许多领域中被用作查找和检查素数的标准方法。当你在网上使用信用卡时，它也在幕后工作着，几乎任何时候安全通信都是在空中或通过电线发送的。
1700496581
1700496582
在米勒和拉宾的成果问世之后的几十年里，我们不知道是否会有一种有效的算法，允许以确定性的方式，用绝对的确定性对素性进行测试。2002年，印度理工学院的三位科学家的确发现了这样一个方法，但像米勒—拉宾这样的随机算法要快得多，因此今天仍在实践中使用。
1700496583
1700496584
对于其他一些问题，随机抽样仍然是唯一已知的有效解决途径。数学中有一个奇特的例子，就是所谓的“多项式身份测试”。“如果你有两个多项式表达式，如2x3+13x2+22x+8，以及（2x+1）×（x+2）×（x+4），找出这些表达式实际上是否为相同的函数（通过算出所有乘法，然后比较结果），这会非常耗时，尤其是随着变量数量的增加。
1700496585
1700496586
在这里，随机性提供了一种可以推进向前的方法：生成一些随机的x并将其代入。如果这两个表达式是不同的，那么如果它们对随机生成的输入给出相同的答案，这将是一个很大的巧合。如果它们对第二个随机输入又给出相同的答案，这将是更大的巧合。如果连续三次随机输入都相同又是更大的巧合。因为没有已知的确定性算法可有效地测试多项式身份，这种随机的方法（重复观测快速接近确定性）是我们可以使用的唯一实际的方法。
1700496587
1700496588
[1]孪生素数是连续奇数，并且都是质数，比如5和7。
1700496589
1700496590
1700496591
1700496592
1700496594
算法之美：指导工作与生活的算法 抽样的优势
1700496595
1700496596
多项式身份测试表明，有时我们的工作是更好地检查随机的价值（从我们想知道的两个表达式中取样），而不是试图理清它们的内部工作。在某种程度上，这似乎相当直观。现在有两种难以区别的设备，要确定它们是两种不同的设备还是两种相同的设备，我们大多数人都会随意地按下按钮，而不是打开箱子来检查线路。而且我们也不会特别惊讶，例如，一个电视中的毒枭只要用刀随机划开货物中的几捆，便可以对整批货物的质量有一定的把握。
1700496597
1700496598
不过，也有一些案例中我们没有使用随机性，也许我们应该用。
1700496599
1700496600
可以说，20世纪最重要的政治哲学家是哈佛大学的约翰·罗尔斯，他为自己设定了一项雄心勃勃的任务：试图协调两个看似对立的关键理念：自由与平等。当一个社会更自由，或者更平等时，它会更“公正”吗？这两者真的必须互相排斥吗？罗尔斯提出了一种他称之为“无知之幕”的问题。他说，想象一下，你即将出生，却不知道自己出生后是怎样的：男人还是女人，富人还是穷人，城市还是农村，有病还是健康。在了解你的地位之前，你必须选择你所生活的社会。你想要什么？罗尔斯认为，拉开无知之幕，对各种社会安排进行评估，我们会更容易对理想中的安排达成共识。
1700496601
1700496602
然而，罗尔斯的思想实验没有考虑到的是，在这样的幕布后面理解一个社会的计算成本。在这种假设下，我们怎么可能希望掌握所有相关信息？暂且不提正义和公正的重大问题，并尝试运用罗尔斯的方法仅仅对例如健康保险条例等提出改变。也许，在美国，出生后成为中西部的一名镇书记的概率，乘以不同的卫生保健计划的分布，这可用在中西部直辖市上，再乘以保险精算数据提供的可能性，例如胫骨骨折的概率，再乘以在中西部医院可能的保险计划所给定的，胫骨骨折的一般处理的平均医疗费用。那么，拟议的保险修订对国家来说是“好”还是“坏”？我们几乎不能指望用这种方式评估一个受伤的心，更不用说数亿人的生命了。
1700496603
1700496604
罗尔斯的哲学批评家们详细地讨论了我们应该如何从无知的面纱中获得信息的问题。例如，我们是否应该尝试尽量扩大平均幸福、中位数幸福、总幸福或别的什么，其中的每一种方法都很著名，但其却将自己置身于有害的反乌托邦之中，如作家厄休拉·勒吉恩所设想的奥米勒斯城的文明——开放。在这个国家里，繁荣与和谐无处不在，一个孩子却被迫生活在悲惨的境地。这些都是应得的批判，而罗尔斯故意回避了这些问题，因为我们不知道如何处理从幕布后面得到的信息。然而，也许更大的问题首先是如何收集这些信息。
1700496605
1700496606
答案很可能来自计算机科学。麻省理工学院的斯科特·阿伦森说，他感到很惊讶，计算机科学家还没有对哲学产生更大的影响。他怀疑，部分原因在于他们“无法将他们所能补充的东西与哲学的概念集合联系起来”。他阐述道：
1700496607
1700496608
人们可能会认为，一旦我们知道某些东西是可计算的，无论计算起来需要10秒还是20秒，这显然是工程师应该关心的，而不是哲学家。但是如果问题是10秒：101010秒，那么这个结论就不太明显了！事实上，在复杂性理论中，我们所关心的数量差距通常是极为巨大的，以至人们也必须考虑到它们的质量差距。例如，这就是看一本400页的书和阅读所有400页的书之间的区别，或者是写下一个千位数字和从1数到那个数的区别。
1700496609
1700496610
计算机科学为我们提供了一种方法来明确评估所有可能的社会规定，例如胫骨受伤。但幸运的是，它还提供了处理这种复杂性的工具。基于抽样的蒙特卡罗算法是该工具箱中最有用的方法之一。
1700496611
1700496612
比如说，当我们需要理解国家医疗改革时，由于它是一个庞大的机构，太复杂而很难轻易理解，我们的政治领导人通常会给我们提供两件事：精心挑选的个人轶事和汇总的统计数据。当然，这些轶事丰富而生动，却不具有代表性。几乎任何一项法律，无论多么开明或具有误导性，都会让一个人过得更好，而另一个人过得更糟，因此精心挑选的故事不会提供更广泛模式的任何观点。另一方面，总的统计数据则恰恰相反：它全面却薄弱。例如，我们可能会了解到，在全美国，平均保费是否下降，但并不是要了解这种变化在一个更细微的层面上是如何产生的：对于大多数人可能会下降，但是奥米勒斯城风格使一些特殊群体（本科生、阿拉斯加人，或孕妇）陷入困境。一个统计数据只能告诉我们部分的故事，它掩盖了任何潜在的异质性。我们甚至不知道我们需要哪些统计数据。
1700496613
1700496614
由于统计数据和政客们最喜欢的故事都不能真正引导我们通过成千上万页的立法提案，因此，一位蒙特卡罗计算机科学家提出了一种不同的方法：抽样。对随机样本进行仔细的检查，可能是一种用以理解太复杂而不能直接理解的东西最有效的方法。当涉及处理质量不可控的问题时，它们棘手而复杂，不能被完全理解，比如单人纸牌或原子裂变、素性测试或公共政策，抽样提供了一种最简单，也是最好的方法来解决问题。
1700496615
1700496616
我们可以看到这种方式与直接给钱的慈善捐助项目类似，它将现金无条件的转移分配给生活在肯尼亚和乌干达的极度贫困的人。它吸引了人们的注意力，在许多层面上重新思考传统的慈善行为：不仅是其不寻常的使命，而且是在其过程中体现出的透明度和问责制。最新的现状显示很成功。
1700496617
1700496618
项目助理丽贝卡·兰格写道：“如果你经常查看我们的网站、博客或脸书主页，你可能已经注意到一些你并不常见的内容：我们收件人的故事和照片。”问题不在于其他慈善机构提供的那些热情洋溢的故事并不真实。准确地说，他们刻意选择展示成功的事例，使得人们不清楚能够获得多少信息。所以，直接给钱的慈善项目决定要对这个传统进行改变。
1700496619
1700496620
每周三，该慈善团队随机挑选一组现金接受者，派出一名工作人员现场采访他们，并逐字逐句地发布工作人员的现场采访记录，无论发生什么都按照此步骤执行。例如，这是他们第一次经历这样的采访，这个女人叫玛丽，她用这笔钱来买铁皮屋顶：[1]
1700496621
1700496622
她能做一间更好的房子，那是一个铁皮房子。她还可以为自己的房子买套沙发。她的生活已经发生了变化，因为以前每当下雨的时候，那个漏水的屋顶就会把房子里的东西都泡在水里。但由于有了资金支持，她才有能力把房子做得更好。
1700496623
1700496624
兰格写道：“我们希望这能让你对所分享的所有类型的信息都有信心，甚至能激发你把其他组织也带到更高的标准。”
1700496625
1700496626
1700496627
1700496628
[
上一页 ]
[ :1.70049658e+09 ]
[
下一页 ]