随机算法与去随机化：图灵奖背后的计算理论主线-北京尧图网络

2023年度图灵奖公布那几天我在几个技术群里看到的反应出奇一致先是有人转了一条新闻链接然后是一串问号最后有人冒出一句“这方向我连标题都读不懂”。这个反馈其实挺真实。图灵奖每年都会上一次热搜但真正让工程师群体有代入感的年份并不多——深度学习、数据库、编译器、操作系统这些方向奖出来的时候大家至少能聊两句“这东西我用过”而2023年度这个奖落在计算理论这条最底层的地基上核心线索是随机性在计算中到底扮演什么角色。说白了它回答的是一个听起来很哲学、实际上每天都在你代码里发生的问题我调用random()到底是在偷懒还是在真的借力这篇东西不是新闻复述。我想以一个写了十几年代码、也被随机算法坑过无数次的从业者身份把这条线的来龙去脉拆开它到底解决了什么问题为什么值得一个终身成就级别的奖对我们这些每天写业务代码、偶尔写点算法的人有什么实际影响以及一个想补课的人该按什么顺序走。无论你是刚入行还在啃算法导论还是已经做了多年系统、对理论早就生疏我都尽量用你熟悉的东西做类比让你看完至少能跟人把这件事讲明白。1. 奖项内核它奖的不是某个算法而是一整套“随机性经济学”先把最容易跑偏的地方掰正。很多人一听“理论计算机科学”脑子里浮现的是那种证明一堆希腊字母、跟现实毫无关系的论文。这个印象有一部分是合理的但用在这一年的奖上并不准确。它表彰的是一条持续了三十多年、横跨复杂度理论、组合数学、密码学、图论的主线工作核心贡献者不是发明了某个具体算法而是反复重塑了我们对“计算能力边界”的理解并且带出了一整套后来被广泛复用的工具。1.1 先把问题问对随机算法到底占了多大便宜设想你要判断一个很大的整数是不是质数或者要在一个巨大的图里找一个割。确定性算法当然有但慢得让人难受如果允许你抛硬币很多问题的解法会瞬间变得简洁漂亮。这就是随机算法的魅力它不保证百分百对只保证“错得极少”而这个“极少”可以压到比你硬盘出错概率还低。问题来了这份便宜是白拿的吗换句话说随机性是不是一种真实的、不可替代的计算资源如果答案是“是”那计算模型里就必须给随机性留一个位置复杂度类的划分要重写如果答案是“不是”那所有随机算法理论上都能被改写成确定性算法只是我们还没找到办法。这条主线上最重要的几项成果恰恰是在“随机性可以被消除”这个方向上推进的它证明的不是“随机算法不好”而是“随机算法能做的事确定性算法原则上也能做前提是某些难题真的难”。这个结论的分量相当于告诉你你手里那张“随机性”信用卡额度也许只是心理安慰。1.2 三个常见误解逐个拆误解一以为这个奖是奖励某个“很厉害的随机算法”。不是。奖励的是对“随机性这一资源本身”的建模与界定。就像经济学奖不会颁给某个具体的促销活动而是颁给对市场机制的理解。误解二以为理论工作离工程很远。我举个身边的例子。你在分布式系统里用哈希做分片、用采样做监控估算、用概率数据结构做去重这些工具的正确性论证全都依赖于“伪随机足够像真随机”这个假设。这条理论线给出的正是这个假设在什么条件下成立、代价是多少。它不是象牙塔它是你脚下那块你从没低头看过的地板。误解三以为“去随机化”意味着以后不用随机数了。恰恰相反。工程上我们几乎不可能真的去掉随机性因为它太便宜了。去随机化的价值在于给出保证让你知道在最坏情况下这个概率算法的失败率是不是真的可控还是只是“跑了一万次没出事”。1.3 为什么这个问题值得一个奖因为它的答案同时改变了三个领域的地形。在复杂度理论里它把“随机性能不能省”变成了一个可以相互推导的命题网络在密码学里它给“伪随机”提供了严格定义让整个现代密码学的安全论证有了落脚点在组合数学里为了造出满足条件的结构人们发展出了一批构造性工具后来被图论、编码理论反复借用。一项工作能在一个领域留下名字就已经难得能同时在三四个领域成为标配工具那就是地基级别的贡献。2. 难度与随机性的对偶为什么“算不出来”反而是好事这条主线里最反直觉、也最漂亮的一步是把“随机性”和“困难性”绑在了一起。听起来像玄学一个问题是难的怎么会帮助我们生成随机数我第一次读到这个思路的时候反应是“这不是把两个麻烦凑一起了吗”。后来想明白它的逻辑反而觉得这是整个理论计算机科学里最优雅的几个想法之一。2.1 直觉版把难题当磨刀石假设存在某类问题任何算法都解不快快到你用再多时间也啃不动。那么这类问题的输出就会表现得“毫无规律”——因为一旦有规律你就能顺着规律把它算出来矛盾。于是一个足够难的函数天然就是一台“规律粉碎机”。利用这一点可以设计出一种生成器输入一小段真正随机的种子输出一大段看起来完全随机的序列。它之所以“看起来随机”是因为如果谁能把它和真随机区分开就等于找到了那个难问题的快速解法。这就是把困难性转化为伪随机性的核心机制。整个论证是归谬式的你区分得出来我就解得开难题你解不开难题你就区分不出来。这一步的意义在于它把两个原本独立的猜想缝在了一起。随机性可以被消除这件事不再是一个孤立的技术问题而是“存在真正难的问题”这个假设的推论。理论工作的价值往往就在这里它不给你一个新工具它给你一张关系图让你知道哪些信念是互相支撑的。2.2 从生成器到算法一条完整的推导链光有生成器还不够得把它接到具体算法上才能说明“随机算法可以被确定性化”。常见的做法叫“条件期望法”思路很朴素随机算法在每一步会做若干随机选择产生若干分支。与其同时探索所有分支不如每次只挑那个“在剩余可能性里期望表现最好”的分支。因为期望是好的所以总存在一条具体路径不差于期望把它挑出来就走完了。这套推导有个前提分支数不能爆炸。所以在接上生成器之前通常要先把随机算法的随机位数量压下来——把“需要一万个随机比特”压成“需要几十个随机比特加一台生成器”。压下来之后穷举所有种子就变得可行了。整条链子是这样的难题存在 → 生成器存在 → 随机位可以压缩 → 穷举种子 → 得到确定性算法。每一环都不复杂串起来就是一个相当强的结论。2.3 一个能抄的计算重复采样到底要跑多少次理论聊完说点马上能用上的。任何靠“多跑几次取多数”来降错误率的方案本质都在用同一个不等式。假设单次实验的估计值偏离真值的概率被控制在某个范围内那么独立重复 n 次取中位数或均值出错概率大致以指数速度下降所需样本量满足下面这个关系n ≥ ln(1/δ) / (2ε²)其中 ε 是你允许的误差幅度δ 是你容忍的失败概率。这个式子非常好用因为它告诉你一件工程上经常被忽略的事精度是平方级昂贵的。下面这张表是我按这个公式算出来的可以直接拿去当参考。允许误差 ε容忍失败率 δ需要的重复次数 n典型场景0.051e-6约 2,800线上监控的粗略比例估计0.011e-6约 69,000需要小数点后两位可信的采样统计0.011e-9约 104,000计费、风控这类错一次就麻烦的场景0.0011e-6约 690 万极高精度估计通常换算法而不是堆样本我第一次认真算这张表是在做一个流量采样统计的功能。当时想当然地把采样率调到千分之一觉得“够准了”结果误差带在业务侧被放大成了一个很难解释的数字。后来老实按公式算样本量再回头调整采样策略问题一下就没了。这就是理论的实际价值它不让你凭感觉猜。3. 工具箱拆开看扩展图、伪随机生成器与零知识这条主线上还带出了三件被反复借用的工具。我把它们放在一起讲是因为它们在思路上是同源的都在用“局部简单、全局难缠”的结构去换一种更强的性质。3.1 扩展图一条边都不多加的“搅拌器”先想象一个社交网络。如果网络里存在明显的两个小圈子消息在里面来回传传很久也出不去这个网络就是“连通性差”的。扩展图要求的是相反的东西每个节点的邻居数量都不多比如固定几条但无论你怎么切分这个网络跨切的边都足够多。效果就是从任意一个点出发随机走几步很快就能“忘记”自己从哪来分布迅速变均匀。它的妙处在于稀疏保证了代价低高连通保证了混合快。在一个 n 个节点的扩展图上随机游走的混合时间通常只要对数级别。这意味着很多需要“快速打散”的场景可以用极低的度数换来极快的收敛。实践中一致性哈希的虚拟节点设计、负载均衡的拓扑构造、乃至某些去中心化系统的邻居选择策略背后都能看到这套思路的影子。真正让这个工具从“存在性证明”走向“可构造”的是一类叫“图乘积”的构造手法把两个小图按某种规则拼起来用很小的度数损失换来扩展性的大幅提升反复迭代就能造出任意规模、度数恒定的扩展图。这类构造后来还被用来解决一个经典问题无向图的连通性判断能不能只用极少的空间完成。答案是可以的而且这个结论在本世纪初被完整地做出来了——用到的正是扩展图这套积木。3.2 伪随机生成器用短种子撑起长序列工程上我们对“伪随机”的理解往往是“用某个线性同余或者梅森旋转生成一串数”。理论上的定义严格得多也更难满足一个生成器算不算伪随机取决于有没有多项式时间的算法能把它和真随机区分开。区分不出来才算伪随机。这个定义带来的直接后果是伪随机不是一个性质而是一个相对概念——相对于你的对手有多强。对手只有有限算力那么一个中等强度的生成器就够用对手算力无限那什么生成器都没用。理解这一点对做工程的人特别重要因为它解释了为什么“同一个随机数生成器在 A 场景很安全在 B 场景就是灾难”不是生成器变了是对手的模型变了。我踩过最典型的一次坑是在一个需要“不可预测”的场景里用了普通的伪随机数生成器。它不是坏的只是它的设计目标是“分布均匀”不是“抗预测”。这两件事在小样本下看起来很像实际上差得很远。后来我把这类需求统一走一个原则只要涉及“不能被猜到”就别用通用随机数用专门的密码学安全生成器只要涉及“统计上均匀”才考虑性能更好的通用方案。这个区分看起来土但救过我不少次。3.3 零知识证明与泄露的边界第三个工具是零知识证明。它的目标听起来自相矛盾我要向你证明我知道某个秘密但我一点秘密的内容都不告诉你。上世纪八十年代中期这个概念被提出来的时候很多人觉得这是个玩具后来人们发现只要存在足够强的单向函数任何数学命题都可以用零知识的方式来证明。这就不是玩具了这是协议设计的基础设施。它的工程意义在于重新定义了“验证”这件事。传统的验证是“你把东西给我看我检查”零知识的路子是“我们做几轮交互我检查你的回答是否自洽但我拿不到东西本身”。带来的直接好处是验证方不必持有敏感数据也能确信对方没有撒谎。这套思路后来演化出了各种变体被用在隐私计算、身份凭证、可验证计算这类场景里。需要泼一盆冷水的是理论上的“存在构造”和工程上的“能用”之间隔着巨大的性能鸿沟。很多方案在论文里是多项式时间实际常数大到无法接受。我见过团队花两个月实现一个漂亮的协议最后因为验证端延迟多了几百毫秒而回滚。这类工作的落地通常要靠后续十几年的工程优化而不是靠理论本身。4. 我怎么看四个判断前面讲的是“它是什么”接下来讲讲我的看法。这部分主观成分多你可以不同意但我尽量把理由摆清楚。4.1 判断一这是地基奖不是应用奖图灵奖的取向一直在这两端之间摆动有时候给一个直接催生了产业的成果有时候给一个把整个学科地基重新浇一遍的成果。这一年属于后者。地基奖的特点是颁完之后你短期内看不到任何产品变化但五年十年之后回头看会发现某个领域的教科书目录被改写了。对从业者的启示是不要用“能不能马上用上”去衡量这类工作。真正的地基工作价值体现在它改变了后来者的默认假设。比如“随机算法不增加多项式时间的计算能力”这个猜想要是被彻底解决整个算法设计的思路都会变——很多为了确定性而做的复杂构造可能变得没必要反过来很多依赖随机性的安全性论证也要重新审视。4.2 判断二它悄悄改了工程实践的默认值我一直觉得理论对工程最大的影响不是给出新算法而是改掉旧的默认值。举几个我亲身感受到的变化。第一个是采样。早年做数据统计大家习惯“抽一部分看看”误差靠经验拍。现在正规一点的团队都会算置信区间和样本量因为公式就摆在那儿不算反而是失职。第二个是哈希。以前选哈希函数看的是“快不快、冲突多不多”现在还要看“抗不抗构造”。因为一旦对手能预测你的哈希碰撞就能被批量制造出来进而把整个数据结构退化成链表。这个认知的普及直接改变了语言标准库的设计取向。第三个是随机数。以前random()一把梭现在至少会问一句“这个场景需要可预测吗”。这个问题的背后就是伪随机性理论给出的那条分界线。这些变化没有一个是某个产品发布会推动的全是慢慢渗透进来的。等你意识到的时候团队里的新人已经默认这么做了。4.3 判断三理论奖项有滞后也有前瞻这个奖有个众所周知的特点表彰的是十几甚至二十几年前的工作。有人吐槽这是“考古奖”我倒觉得这个滞后是合理的。理论成果需要时间被消化、被验证、被其他领域借用才能真正证明它的分量。太早颁奖容易押错宝。但滞后也带来一个副作用公众看到的是一群“突然获奖”的人看不到的是他们背后那条长长的、由无数未获奖者共同铺就的路。理论计算机科学尤其如此很多关键引理是某个博士生的毕业论文里顺手做出来的几十年后才被大规模引用。所以我在看这类新闻时习惯把它当成一个“领域地图”来看获奖方向本身就说明了这个领域过去三十年最硬的骨头在哪儿。4.4 判断四别急着把 PBPP 当现实最后这个判断有点扫兴但我觉得必须说。这条主线上最著名的猜想之一大致是说随机性不增强计算能力。很多科普文章会写成“随机算法没什么用都能改成确定的”。这个说法在数学上是有条件的在工程上更是容易误导。条件在于整个推导依赖“存在真正难的问题”这个假设。这个假设本身没被证明而且有一派观点认为它可能不成立。工程上的误导在于即使理论上可以确定性化那个确定性算法的常数因子常常大到无法接受。就像理论上所有程序都能写成一行 lambda 表达式但你不会真的那么写。所以我的态度是把这类结论当成方向性指引而不是施工图纸。它告诉你“随机性不是魔法是有代价的资源”这就够了它没告诉你“明天就把random()删了”。5. 想下场的人怎么走一条压缩到三个月的路径说完看法给点实在的。我知道很多人看完这类新闻的反应是“想学但不知道从哪儿进”。这条线确实门槛不低但也没那么吓人。我给一条我自己验证过的路径按三个月、每周十小时左右的强度设计。5.1 知识地图与顺序第一步先把“概率”捡回来。不是统计学那套是概率论的基本功期望的线性性、马尔可夫不等式、切比雪夫不等式、切尔诺夫界。这几个工具能覆盖你八成以上的分析需求而且都不难一两个周末足够。切比雪夫不等式之所以重要是因为它几乎不要求独立性工程上很多弱相关场景只能靠它硬顶。第二步补复杂度理论的最小集。不用一上来就啃厚书先把几个类搞清楚多项式时间、随机多项式时间、对数空间、非确定性对数空间以及它们之间已知的包含关系。搞清楚“随机多项式时间是不是等于多项式时间”这个问题的地位你就理解了这一年的奖在讲什么。第三步看构造。扩展图、伪随机生成器、零知识证明这三个各看一篇综述就够不必啃原始论文。重点是理解它们各自“用什么换什么”扩展图用度数换连通性生成器用种子换长度零知识用交互轮数换信息隐藏。第四步动手。这一步最容易被跳过也最不该跳过。下面给一个能跑的实验。5.2 用代码把直觉跑出来这个脚本做两件事验证重复采样降误差的速度是不是真的按指数走以及观察随机游走在不同结构图上的混合速度差异。跑一遍你对前面那些公式的体感会完全不一样。import random import math def estimate_error_rate(trials, samples_per_trial, p_true0.5, eps0.05): 重复 sampling统计估计值偏离真值超过 eps 的频率 bad 0 for _ in range(trials): hits sum(1 for _ in range(samples_per_trial) if random.random() p_true) est hits / samples_per_trial if abs(est - p_true) eps: bad 1 return bad / trials # 观察样本量增加时失败率如何快速下降 for n in [10, 50, 200, 1000, 5000]: rate estimate_error_rate(trials2000, samples_per_trialn, eps0.05) bound math.exp(-2 * n * 0.05 ** 2) print(fn{n:5d} 实测失败率{rate:.4f} 理论上界{bound:.4f}) def walk_mixing(n_nodes, degree, steps, trials2000): 在环状图与随机正则图上做随机游走比较分布偏差 # 环状图每个点只连左右邻居混合极慢 ring {i: [(i - 1) % n_nodes, (i 1) % n_nodes] for i in range(n_nodes)} # 近似正则随机图每个点随机连 degree 个不同邻居 rand_graph {} for i in range(n_nodes): neighbors set() while len(neighbors) degree: j random.randrange(n_nodes) if j ! i: neighbors.add(j) rand_graph[i] list(neighbors) def deviation(graph): counts [0] * n_nodes for _ in range(trials): cur 0 for _ in range(steps): cur random.choice(graph[cur]) counts[cur] 1 uniform trials / n_nodes return sum(abs(c - uniform) for c in counts) / (2 * trials) return deviation(ring), deviation(rand_graph) ring_dev, rand_dev walk_mixing(n_nodes200, degree4, steps20) print(f环状图 20 步后偏差: {ring_dev:.4f}) print(f随机正则图 20 步后偏差: {rand_dev:.4f})跑完你会看到两个现象。第一失败率随样本量下降的速度远比线性快但也没有快到“随便加点样本就行”的程度ε 缩小十倍样本量要涨一百倍。第二在环状图上走二十步位置几乎还停留在起点附近在度数相同但连接随机的图上二十步之后分布已经相当均匀。这就是“度数一样、结构不同、性质天差地别”的直观演示也是扩展图存在的意义。5.3 我踩过的坑第一个坑是把渐近复杂度当性能承诺。理论文章说某算法是多项式时间我一开始以为可以直接上线结果实现出来比原有方案慢三个数量级。后来学乖了看理论结果先看常数看常数先看有没有实现报告。第二个坑是混淆“期望好”和“大概率好”。一个算法期望复杂度是线性的不代表它不会在某一批输入上炸掉。工程上要的是尾部行为不是均值。看到期望分析一定追问一句“方差多大、最坏多坏”。第三个坑是过度迷信随机性。有段时间我什么都要加点随机化觉得这样“更健壮”。实际上随机化是有成本的不可复现、难调试、测试用例不好写。后来我的原则变成——能用确定性方案解决且性能可接受就别引入随机只有在对抗性输入明显、或者确定性方案复杂度差一个量级时才动这个念头。6. 概念速查与常见误解最后整理一份速查方便你以后跟人聊的时候不卡壳。6.1 一张容易混的表概念一句话解释常见误用随机算法允许抛硬币、以高概率给出正确答案的算法以为它“可能出错所以不能用”其实错率可以压到极低去随机化把随机算法改写成不抛硬币的确定性算法以为实践中必须这么做其实多数场景没必要伪随机生成器用短种子生成长串且与真随机不可区分以为“看着乱”就是伪随机其实要看抗区分能力扩展图度数低但连通性极强的图以为只是图论玩具其实负载均衡、编码都在用零知识证明证明自己知道某事但不泄露内容以为等于“什么都不说”其实要交互多轮单向函数正向好算、反向难解的函数以为难解是绝对的其实只是“目前没找到快算法”6.2 学习中的高频卡点卡点一总想找“标准答案”。这条线上大量结论是条件式的——“如果 A 成立那么 B 成立”。新手容易不耐烦觉得“到底成不成立给个准话”。但条件式结论本身就是成果它告诉你哪些猜想是同生共死的。卡点二把归谬论证当循环论证。看到“假设有快速解法则能区分伪随机矛盾”很多人第一反应是“这不就是假设自己吗”。其实不是归谬的每一步都要真的构造出东西来构造的可行性才是难点。卡点三忽视组合工具的基本功。这条线上的很多证明难点不在概率在组合构造怎么切、怎么拼、怎么算边界。这部分没有捷径只能多做几道题。卡点四读综述跳过引理。综述里的引理往往一句话带过但那一句话可能是几十页的技术核心。我的建议是第一遍读确实可以跳但要标记下来等你需要用到这个结论时老老实实回去把那篇原始论文的对应章节啃完。我个人在实际操作中的体会是这类看似“离得很远”的理论真正有用的地方不在于它给了你什么新工具而在于它帮你建立了一套判断标准什么时候该相信一个概率保证什么时候该怀疑一个“跑了很多次都没出错”的经验结论什么时候该承认自己手里的随机数根本不随机。这套标准不会让你的代码变短但会让你的判断变稳。

随机算法与去随机化：图灵奖背后的计算理论主线

相关推荐

Claude隐式记忆机制解析与工程化实践

基于YOLOv5的道路坑洼检测系统设计与实现

基于多目标粒子群算法的水下图像增强技术

更多资讯

Hermes Agent本地开发实操：从setup到可调试运行

三维透视模型技术在智能仓储管理中的应用与实现

光子晶体连续域束缚态远场偏振的COMSOL仿真与Matlab后处理

端到端测试实战：从用例设计到稳定性优化

端到端测试实战指南：从E2E选型到稳定维护

e2e profile1实战：从端到端测试到分层落地与稳定性治理

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？