马里奥救公主比金融加密还难解？

你玩过超级马里奥吗？那位来自布鲁克林的水管工，穿过下水道、踩扁蘑菇怪，一路狂奔去救桃子公主。这个游戏看起来就是个童话，但你有没有想过：从起点到城堡，马里奥真的能到达吗？科学家最近给出了一个让你意外的答案——在某些设计出来的关卡里，这个问题竟然和破解我们的银行交易密码一样复杂，甚至计算机都算不出来答案。

这可不是随便说说。麻省理工学院有一个叫“硬度小组”的团队，名字听上去很正式，其实并不是官方的研究机构。它更像是个临时的名号，放在理论计算机科学的几个项目上，好几个都跟超级马里奥有关。这些项目来自埃里克·德梅因教授的课程“算法下界：硬度证明的乐趣”。德梅因是计算机科学的教授，拿过麦克阿瑟奖，也就是俗称的“天才奖”，研究计算几何，方向是蛋白质折叠和折纸。但他也研究复杂度理论，就是一门给问题分科的学问：按照计算机解题需要花多少时间和记忆空间，把它们整理进不同的类别里。

德梅因还是个超级马里奥的铁粉。他说：“我是玩任天堂红白机游戏长大的。小时候花了好多时间在这些游戏上，所以这么多年后能把它们跟自己的研究绑在一起，特别有意思。”就是这种个人兴趣，让他和合作者花了十几年，把水管工闯关变成了严肃的数学对象。

我们先回到超级马里奥本身。游戏在一个水平滚动的世界里展开，有平台、管道和各种障碍。目标是营救蘑菇王国的统治者桃子公主，你得一关一关地跑，躲开或踩扁那些挡路的蘑菇怪——它们叫板栗仔，还有刺猬一样的刺壳龟。初代版本里，每关结束都有一根旗杆，马里奥碰上去就进入下一段旅程。这听上去简单，玩起来也不觉得有什么不对。可是在计算机科学的眼光里，这就成了一个抽象的图景：马里奥在横轴上移动，遇见各种敌人和机关，他的跳跃和踩踏动作构成了解决问题的手段。问题就是：给定一个自定义的关卡，马里奥到底能不能到达旗杆，或者城堡？

这就进入了复杂度理论的范畴。过去十四年里，德梅因和他的合作者已经证明了许多关于超级马里奥的事情。比如说，算出马里奥能否过关，竟然比那个著名的旅行商问题还要棘手。旅行商问题是什么？想象一个快递员要跑遍几十个城市，每两个城市之间都有道路，他想找一条最短的总路线。城市越多，可能的走法就指数级增加，计算机找最优解的速度会变得极慢。超级马里奥的闯关问题，在复杂度层级图上站的位置比它更高，意味着更难。甚至比大数的因子分解问题也不逊色。因子分解有多难？我们每天网上银行、支付密码的安全性，就建立在没法很快把一个极大数分解成两个质数乘积的基础上。到现在，这还是个假设——没人证明它绝对不可解，可也没人找到快速算法。马里奥闯关的难度，至少就站在这个层次上。

不过，真正让德梅因都惊讶的结果来自他的四个学生。在二〇二三年的那堂课上，海耶什·阿尼、霍尔登·霍尔、里卡多·鲁伊斯和纳文·文卡特组成小组，完成了期末项目。他们用一群粉丝制作的超级马里奥关卡编辑器，结合一个叫“超级马里奥制作器”的平台，建构出了一些特殊关卡。这些关卡硬生生把闯关问题推到了“不可判定”的边界。不可判定是什么意思？就是在逻辑上，我们不可能写出一段电脑程序，让它永远正确地预测：在这些关卡里，马里奥到底能不能走到城堡。

我们深入看看这种不可判定性。普通的电脑游戏里，敌人怎么移动、台阶怎么摆放，都是固定的套路。计算机会一步一步模拟马里奥的动作，迟早能试出有没有路可达。但如果关卡复杂到一定程度，问题就不再是“能不能算出来”，而是“逻辑上就不存在一个普适的算法”。这就像有人问你：“这句话是假的。”如果这句话是真的，那它说的又是假的；如果它是假的，那它又说对了。没有任何程序能稳定地给出答案。超级马里奥的某些关卡就被建造成了这样一类结构，迫使计算机钻进逻辑的死循环。

你可能想说，游戏里不是可以一条条路去试吗？关键在于，这些学生造的关卡里，障碍的排列方式模拟了抽象的数学机器，比如图灵机的计算过程。图灵机是计算机的原型概念，可以执行任何形式的计算。如果某个图灵机会停止，马里奥就能过关；如果它不会停，马里奥就永远走不到终点。而停机问题，就像刚才说的自指语句，已经被证明是不可判定的。学生们极其巧妙地把这种逻辑困境，翻译成了蘑菇、管道和跳跃的动作。于是，预测马里奥能否成功，就相当于要解出一个根本解不出的数学谜。

这个发现把游戏和金融安全挂上了钩。银行交易加密的根基是大数分解问题，没人能证明它绝对难倒计算机，可目前也没有高效的解法。马里奥闯关问题至少跟它一样深。也就是说，假如有一天有人找到了破解密码的方法，也可能会顺手解决马里奥的关卡谜题。反过来，假如我们能证明马里奥关卡绝对不可判定，那也可能对加密理论带来更深的理解。二者在数学结构的底层共享着一片黑暗森林。

德梅因回忆起自己的游戏时光说，当年握着任天堂红白机手柄打水管工时，从没想过跳跃和踩踏能藏着这么深的数学。更没预想到，那批学生的作业能在复杂度理论上划出一条清楚的刻痕。如今，研究团队还在继续挖掘各类经典游戏里的计算难度，从俄罗斯方块到口袋妖怪，都成了理论计算机科学的试验田。每个关卡就像是给电脑出的一道智力题，有些题有解，有些题可能永远悬在半空。

最后的悬念还留在那批学生制造的关卡里。它们并没有超出超级马里奥的视觉范围，蘑菇还是那个像素蘑菇，管道还是那个绿色管道，可背后的数学已经漫入了未知领域。也许有一天，有人会设计出新的数学工具来破解它们；也许，就像某些逻辑悖论，会永远留给水管工一个到不了的城堡。这正是复杂度理论迷人之处：在跳跃和踩扁的童趣背后，藏着一个和世界最严谨的计算问题同等硬核的故事。