这里有一个你可能在学校没有解决的问题：你是来自布鲁克林的一个有抱负的年轻管道工，生活在一个被名为库巴的暴力人形蘑菇所占据的世界里。你生命中的挚爱被绑架，于是你踏上了拯救她的旅程，穿越充满管道和怪物的地形，在那里你唯一的保护手段就是你的跳跃和踩踏能力。这是一段如此艰难的旅程，以至于没有任何计算机——无论是真实的还是假想的——能够计算出你能否到达她那里。根据麻省理工学院难度组发布的研究，判断你的任务是否可能至少和解码金融交易背后的加密一样复杂。但是如果这个问题能说话，它首先会说：“你好，我是马里奥！”虽然麻省理工学院难度组有一个YouTube频道，但它并不是一个正式的研究小组。相反，它是一个理论计算机科学项目的占位符名称——包括几个与超级马里奥相关的项目——出自埃里克·德梅因的课堂《算法下界：与难度证明乐趣》。德梅因是一位计算机科学教授，因其在蛋白质折叠和折纸方面的计算几何学工作获得了麦克阿瑟奖学金（也称为“天才”奖）。但他也研究复杂性理论，专注于根据计算机解决问题所需的时间和内存空间将问题归类。他恰好也是超级马里奥的狂热粉丝。“我小时候玩NES（任天堂娱乐系统）游戏长大，”德梅因说。“我花了许多小时在游戏上，所以多年后回到它并将其与我的研究结合在一起是一件很有趣的事。”埃里克·德梅因研究复杂性理论，考察计算机解决问题所需的时间和内存。他也是超级马里奥的狂热粉丝。超级马里奥发生在一个水平滚动的宇宙中，平台、管道和其他障碍物。游戏的目标是通过这个地形拯救蘑菇王国的公主桃子，期间躲避或与怪物（如库巴和被称为刺猬的致命刺猬对决）。游戏分为多个关卡；在原版中，每个关卡结束时都有一个旗杆，将马里奥送到使命的下一个部分。在过去的14年中，德梅因和他的合作者已经证明超级马里奥的许多事情，例如它比臭名昭著的旅行商问题（寻求不同地点之间的最有效路线）或大数分解问题更难。但最让德梅因惊讶的结果来自他的四名学生：林安妮 '21，MEng '23；霍尔登·霍尔 '26；里卡多·鲁伊斯 '24，MEng '25；以及纳维恩·文卡特 '23，MEng '24。为了2023年那门课的最终项目，团队使用了一系列由粉丝制作的超级马里奥关卡编辑器和一个名为超级马里奥制造者的平台，创建了难度如此之大的关卡，以至于无法判断换句话说，不可能编写计算机程序来始终准确预测马里奥是否能够到达城堡。之前，德梅因认为超级马里奥属于PSPACE复杂性类，该类包含可解问题，但随着问题的增大，其解决方案变得不切实际。那时，他甚至说PSPACE是马里奥的“永久家园”。但新的发现将超级马里奥推入了RE-Complete，无法决定的问题类。“这是我们能想象到的这类游戏中最难的复杂性类，”德梅因说。计算机无法解决的问题在1936年，现代计算机科学之父阿兰·图灵创造了一个如今被称为停机问题的难题，以证明不可能构建能够解决一切问题的计算机。停机问题的核心是一个悖论，它是这样的：假设你有一台华丽的计算机，称为Oracle，它能够查看任何程序并正确判断跟随它的计算机会不会停止。例如，如果它看到程序“取1并加3”，Oracle会说程序会停止，但如果程序说“取1并加1直到它变为0”，Oracle会说它会永远运行。现在假设你有另一台计算机，名为Contrarian，你将Oracle放在其中。当你向Contrarian提供一个程序时，它会将其传递给Oracle，然后做出与Oracle所说的程序将要做的相反的事情。因此，如果Oracle评估Contrarian的程序并认为它将停止，Contrarian将永远运行。如果Oracle认为该程序将永远运行，Contrarian将停止。无论哪种情况，Oracle的评估都是错误的，因此分类问题是不可决定的。证明超级马里奥不可决定的证据依赖于这种思想的更复杂版本。团队的论点使用一种称为还原的技术对视频游戏进行分解，