摘要：时间和内存（空间）是计算中最基本的两种资源，每个算法都需要一些时间来运行，并且在运行时需要一些空间来存储数据。迄今为止，已知的算法里所需的空间与其运行时间基本上都成正比，研究人员认为没有更好的办法。
一个计算机领域的著名问题，在停滞50年之后终于有了进展。
MIT科学家威廉姆斯一次偶然发现：证明内存比大家认为的更强大。在所有可以想象的计算中，少量的内存与大量的时间一样有价值。
时间和内存（空间）是计算中最基本的两种资源，每个算法都需要一些时间来运行，并且在运行时需要一些空间来存储数据。迄今为止，已知的算法里所需的空间与其运行时间基本上都成正比，研究人员认为没有更好的办法。
但现在威廉姆斯证明，存在一个数学程序，可以将任何算法转换成「占用更少空间」的形式。
由于想法过于不可思议，他当时第一想法是：大概是自己疯了吧。
于是开始着手证明自己错了，但想了几个小时也没找出任何瑕疵：没准万一真就自己对了呢。
经过几个月的整理和推敲，最终将成果po到网上，没想到收获大家一种好评。
一华盛顿大学科学家表示：这是一个相当惊人的结果，也是一个巨大的进步。
先来看看这是一个什么问题。
如果用大白话来讲，这个问题其实源于我们一种直觉：你可以重复使用空间，但不能重复使用时间。
算法可以反复使用同一小块内存，而时间却不那么宽容，一旦过去，就无法再收回。
但对于正经科学家来说，直觉是不够的，这需要严谨的证明！
哎，这就难到科学家了，没成想一难就难了半世纪。（Doge）
威廉姆斯所在的领域是计算机科学一个分支学科计算复杂性理论。
这个领域就是解决诸如列表排序或因式分解等计算问题所需的资源（例如时间和空间）。大多数问题可以通过多种不同的算法来解决，每种算法对时间和空间都有各自的需求。复杂性理论家根据最佳算法（即运行速度最快或占用空间最少的算法）的资源需求，将问题划分为不同的类别，称为复杂性类别。
但是，如何让计算资源的研究实现数学上的严谨程度呢？如果只是单纯地分析时间和空间，那是不可能的。要想取得进展，首先需要正确的定义。
20世纪60年代，计算机科学家哈特马尼斯建立了用来分析时间和空间的精确定义——P，涵盖了所有可以在合理时间内解决的问题。空间领域的一个类似复杂性类别被称为“PSPACE”。
这两类问题之间的关系是复杂性理论的核心问题之一。P 中的所有问题也都属于 PSPACE 问题，因为快速算法根本没有足够的时间填满计算机内存中的大量空间。
如果反过来也成立，那么这两个类将是等价的：空间和时间将具有相当的计算能力。
但科学家们怀疑 PSPACE 是一个更大的类，包含许多 P 中没有的问题。换句话说，他们认为空间是一种比时间更强大的计算资源。
为了证明PSPACE大于P，研究人员必须证明，对于PSPACE中的某些问题，快速算法绝对不可能实现。
1965年，哈特马尼斯搬到了康奈尔大学，担任新成立的计算机科学系主任。在他的领导下，该系迅速发展成为复杂性理论的研究中心。
20世纪70年代初，那里的两位研究人员约翰·霍普克罗夫特和沃尔夫冈·保罗着手建立时间和空间之间的精确联系。
他们知道，要解决 P 与 PSPACE 的问题，就必须证明在有限的时间内无法完成某些计算。但要证明这一点却很难。
因此，他们决定反过来思考这个问题，探索有限空间下能做什么。他们希望证明，给定一定空间预算的算法可以解决与时间预算稍长的算法相同的所有问题。这表明空间至少比时间略胜一筹——这是证明 PSPACE 大于 P 的一个小而必要的步骤。
为了实现这一目标，他们转向了一种“模拟”方法，即将现有算法转化为解决相同问题的新算法，但所需的空间和时间有所不同。
有个通俗的例子，你得到了一个快速算法，可以按字母顺序排列书架，但它需要你把书堆成几十个小堆。你可能更喜欢一种占用公寓空间更少的方法，即使它需要更长的时间。
模拟是一种数学过程，你可以用来得到更合适的算法：输入原始算法，它会给出一个新的算法，以节省空间但牺牲时间。
他们俩想要开发一种通用的模拟程序，可以适用于所有算法，哪怕只是节省一点点空间。时间来到1975年， 在一个年轻研究员瓦利安特参与下，他们仨终于把这个想法实现了。
但随后进展停滞，复杂性理论家开始怀疑他们遇到了一个根本性的障碍。问题恰恰在于模拟的普适性和通用性。
虽然许多问题可以用比时间少得多的空间来解决，但有些问题直观上似乎需要几乎与时间一样多的空间。而且当时的作者保罗Paul与合著者也很快证明确实不可能实现普适性。
于是这个问题就这样持续了50年都没有解决。
1996年，他来到了康奈尔大学，追随哈特马尼斯的脚步。
他自从大学第一次遇到这个问题以来就一直着迷，他甚至在计算机科学课程之外还学习了逻辑学和哲学课程，试图从其他时间和空间视角中寻找灵感，但最终却徒劳无功。
一次转机是在2010年另一个关于计算记忆问题的进展：哪些问题可以用极其有限的空间来解决？
2010 年，复杂性理论先驱 Stephen Cook 和他的同事发明了一项名为“树评估问题”的任务。他们证明了，任何空间预算低于特定阈值的算法都不可能实现这一点。但这其中存在一个bug。该证明依赖于保罗和他的同事几十年前提出的一个常识性假设：算法无法将新数据存储在已满的空间中。
十多年来，科学家们一直试图弥补这一bug。结果在2023年，Cook的儿子和他的工作伙伴，设计了个算法解决了树评估问题，结果发现占用的空间比任何人想象的都要少得多。
老Cook将数据比做鹅卵石，无法挤压，必须在算法的内存中占据不同的位置。但事实证明，这并非存储数据的唯一方式，可以将这些鹅卵石想象成可以稍微挤压在一起的东西。
威廉姆斯在一堂课上灵光乍现：
诶那既然数据可以挤压，这是不是这个方法就相当于是个可以减少空间内存的通用工具了！经过进一步研究发现，这种模拟可以让新算法的空间占用大大减少——大约等于原始算法时间预算的平方根。
这种新的节省空间的算法也会慢得多，因此该模拟不太可能有实际应用。但从理论角度来看，这无疑是革命性的。
然后，他仅用几行数学运算，就反过来证明了时间计算能力的一个消极结果：至少有一些问题除非使用的时间多于空间，否则无法解决。第二个范围更窄的结果与研究人员的预期一致。
从定性角度来看，威廉姆斯的第二个结果听起来像是人们长期寻求的P与PSPACE问题的解决方案。
两者的区别在于规模。
P和PSPACE是非常广泛的复杂性类别，而威廉姆斯的结果则在更精细的层面上进行。
不要要证明PSPACE大于P，研究人员必须进一步扩大这一差距。但威廉姆斯花了几个月的时间尝试扩展都失败了。
半世纪前参与通用模拟的那个年轻研究员瓦利安特，目前他在哈佛大学任教，他表示
这可能是一个终极瓶颈，也可能是一个持续50年的瓶颈。
又或者下周就可能解决。
不过现在看46岁的他取得了很大的进展，但几十年前也曾被老师转方向。
威廉姆斯童年住在阿拉巴马州乡村，那里有一个50英亩大的农场。
7岁时第一次见到电脑，当时他的母亲开车带他穿过县城去参加一个特殊的学术强化班。他回忆说，当时一个用于生成数字烟花表演的简单程序让他着迷——
随机选取一种颜色，然后从显示器中央向随机方向发送。「你永远无法预测最终会得到一个什么样的图像」。
这正是那时候开始，他就产生了浓厚的兴趣，没有计算机那就在纸上写程序，父母也不知道拿他怎么办。
高中最后两年，他转学到阿拉巴马数学与科学学校，在那里他第一次接触到计算机科学的理论知识，也第一次确定了想做的事情：
我意识到外面的世界更加广阔，而且有办法用数学的方式思考计算机。
而到了申请大学的时候，他知道攻读复杂性理论需要远离家乡，但他的父母明确表示，西海岸和加拿大是不可能的。在剩下的选择中，康奈尔大学脱颖而出。
于是他凭借丰厚的经济资助，来到了这个梦中情地，这个理论的起始之地康奈尔大学。
不过到了大二，他就很难跟上课程了。他在一门计算理论课上只得到了中等成绩，老师建议他考虑其他职业。
但他不肯，决定加倍努力，修了一门研究生理论课，希望在这门难度更大的课上取得优异的成绩，能让他研究生申请时显得格外突出。
而教授这门研究生课程的教授正是哈特马尼斯，彼时他已是该领域的元老级人物。
威廉姆斯开始每周参加哈特马尼斯的办公室课程，几乎总是唯一到场的学生。他的坚持得到了回报：他在课程中获得了A，哈特马尼斯也同意在下个学期指导他完成一个独立研究项目。
大学期间，他们两个一直保持着每周的会面。哈特马尼斯鼓励他培养一种个性化的复杂性研究方法，并引导他避开死胡同。
在这之后他始终在研究复杂性理论。2010年，他证明了一个里程碑式成果，被认为是朝着P与NP问题解决迈进。
这一成果巩固了威廉姆斯的声誉，他随后又撰写了数十篇关于复杂性理论不同主题的论文。
不过，P 对 PSPACE 这个问题一直在他脑海中挥之不去：我只是想不出什么足够有趣的东西。
这就是真·念念不忘，必有回响吧。
参考链接：
阅读最新前沿科技趋势报告，请访问欧米伽研究所的“未来知识库”
未来知识库是“欧米伽未来研究所”建立的在线知识库平台，收藏的资料范围包括人工智能、脑科学、互联网、超级智能，数智大脑、能源、军事、经济、人类风险等等领域的前沿进展与未来趋势。目前拥有超过8000篇重要资料。每周更新不少于100篇世界范围最新研究资料。欢迎扫描二维码或访问进入。
牛津未来研究院 《将人工智能安全视为全球公共产品的影响、挑战与研究重点》
麦肯锡：超级智能机构：赋能人们释放人工智能的全部潜力
AAAI 2025 关于人工智能研究未来研究报告
斯坦福：2025 斯坦福新兴技术评论：十项关键技术及其政策影响分析报告（191 页）
壳牌：2025 能源安全远景报告：能源与人工智能（57 页）
盖洛普 & 牛津幸福研究中心：2025 年世界幸福报告（260 页）
Schwab ：2025 未来共生：以集体社会创新破解重大社会挑战研究报告（36 页）
IMD：2024 年全球数字竞争力排名报告：跨越数字鸿沟人才培养与数字法治是关键（214 页）
DS 系列专题：DeepSeek 技术溯源及前沿探索，50 页 ppt
联合国人居署：2024 全球城市负责任人工智能评估报告：利用 AI 构建以人为本的智慧城市（86 页）
TechUK：2025 全球复杂多变背景下的英国科技产业：战略韧性与增长路径研究报告（52 页）
NAVEX Global：2024 年十大风险与合规趋势报告（42 页）
《具身物理交互在机器人 - 机器人及机器人 - 人协作中的应用》122 页
2025 - 2035 年人形机器人发展趋势报告 53 页
Evaluate Pharma：2024 年全球生物制药行业展望报告：增长驱动力分析（29 页）
【AAAI2025 教程】基础模型与具身智能体的交汇，350 页 ppt
Tracxn：2025 全球飞行汽车行业市场研究报告（45 页）
谷歌：2024 人工智能短跑选手（AI Sprinters）：捕捉新兴市场 AI 经济机遇报告（39 页）
【斯坦福博士论文】构建类人化具身智能体：从人类行为中学习
《基于传感器的机器学习车辆分类》最新 170 页
美国安全与新兴技术中心：2025 CSET 对美国人工智能行动计划的建议（18 页）
罗兰贝格：2024 人形机器人的崛起：从科幻到现实：如何参与潜在变革研究报告（11 页）
兰德公司：2025 从研究到现实：NHS 的研究和创新是实现十年计划的关键报告（209 页）
康桥汇世（Cambridge Associates）：2025 年全球经济展望报告（44 页）
国际能源署：2025 迈向核能新时代
麦肯锡：人工智能现状，组织如何重塑自身以获取价值
威立（Wiley）：2025 全球科研人员人工智能研究报告（38 页）
牛津经济研究院：2025 TikTok 对美国就业的量化影响研究报告：470 万岗位（14 页）
国际能源署（IEA）：能效 2024 研究报告（127 页）
Workday ：2025 发挥人类潜能：人工智能（AI）技能革命研究报告（20 页）
CertiK：Hack3D：2024 年 Web3.0 安全报告（28 页）
世界经济论坛：工业制造中的前沿技术：人工智能代理的崛起》报告
迈向推理时代：大型语言模型的长链推理研究综述
波士顿咨询：2025 亚太地区生成式 AI 的崛起研究报告：从技术追赶者到全球领导者的跨越（15 页）
安联（Allianz）：2025 新势力崛起：全球芯片战争与半导体产业格局重构研究报告（33 页）
IMT：2025 具身智能（Embodied AI）概念、核心要素及未来进展：趋势与挑战研究报告（25 页）
IEEE：2025 具身智能（Embodied AI）综述：从模拟器到研究任务的调查分析报告（15 页）
CCAV：2025 当 AI 接管方向盘：自动驾驶场景下的人机交互认知重构、变革及对策研究报告（124 页）
《强化学习自我博弈方法在兵棋推演分析与开发中的应用》最新 132 页
《面向科学发现的智能体人工智能：进展、挑战与未来方向综述》
全国机器人标准化技术委员会：人形机器人标准化白皮书（2024 版）（96 页）
美国国家科学委员会（NSB）：2024 年研究与发展 - 美国趋势及国际比较（51 页）
艾昆纬（IQVIA）：2025 骨科手术机器人技术的崛起白皮书：创新及未来方向（17 页）
NPL&Beauhurst：2025 英国量子产业洞察报告：私人和公共投资的作用（25 页）
IEA PVPS：2024 光伏系统经济与技术关键绩效指标（KPI）使用最佳实践指南（65 页）
AGI 智能时代：2025 让 DeepSeek 更有趣更有深度的思考研究分析报告（24 页）
2025 军事领域人工智能应用场景、国内外军事人工智能发展现状及未来趋势分析报告（37 页）
华为：2025 鸿蒙生态应用开发白皮书（133 页
《超级智能战略研究报告》
中美技术差距分析报告 2025
欧洲量子产业联盟（QuIC）：2024 年全球量子技术专利态势分析白皮书（34 页）
美国能源部：2021 超级高铁技术（Hyperloop）对电网和交通能源的影响研究报告（60 页）
罗马大学：2025 超级高铁（Hyperloop）：第五种新型交通方式 - 技术研发进展、优势及局限性研究报告（72 页）
兰德公司：2025 灾难性网络风险保险研究报告：市场趋势与政策选择（93 页）
GTI：2024 先进感知技术白皮书（36 页）
AAAI：2025 人工智能研究的未来报告：17 大关键议题（88 页）
安联 Allianz2025 新势力崛起全球芯片战争与半导体产业格局重构研究报告
威达信：2025 全球洪水风险研究报告：现状、趋势及应对措施（22 页）
兰德公司：迈向人工智能治理研究报告：2024EqualAI 峰会洞察及建议（19 页）
哈佛商业评论：2025 人工智能时代下的现代软件开发实践报告（12 页）
德安华：全球航空航天、国防及政府服务研究报告：2024 年回顾及 2025 年展望（27 页）
奥雅纳：2024 塑造超级高铁（Hyperloop）的未来：监管如何推动发展与创新研究报告（28 页）
HSOAC：2025 美国新兴技术与风险评估报告：太空领域和关键基础设施（24 页）
Dealroom：2025 欧洲经济与科技创新发展态势、挑战及策略研究报告（76 页）
《无人机辅助的天空地一体化网络：学习算法技术综述》
谷歌云（Google Cloud）：2025 年 AI 商业趋势白皮书（49 页）
《新兴技术与风险分析：太空领域与关键基础设施》最新报告
150 页！《DeepSeek 大模型生态报告》
军事人工智能行业研究报告：技术奇点驱动应用加速智能化重塑现代战争形态 - 250309（40 页）
真格基金：2024 美国独角兽观察报告（56 页）
璞跃（Plug and Play）：2025 未来商业研究报告：六大趋势分析（67 页）
国际电工委员会（IEC）：2025 智能水电技术与市场展望报告（90 页）
RWS：2025 智驭 AI 冲击波：人机协作的未来研究报告（39 页）
未来今日研究所 2025 年科技趋势报告第 18 版 1000 页
模拟真实世界：多模态生成模型的统一综述
中国信息协会低空经济分会：低空经济发展报告（2024 - 2025）（117 页）
浙江大学：2025 语言解码双生花：人类经验与 AI 算法的镜像之旅（42 页）
人形机器人行业：由 “外” 到 “内” 智能革命 - 250306（51 页）
大成：2025 年全球人工智能趋势报告：关键法律问题（28 页）
北京大学：2025 年 DeepSeek 原理和落地应用报告（57 页）
欧盟委员会 人工智能与未来工作研究报告
加州大学伯克利分校：面向科学发现的多模态基础模型：在化学、材料和生物学中的应用
电子行业：从柔性传感到人形机器人触觉革命 - 250226（35 页）
RT 轨道交通：2024 年中国城市轨道交通市场数据报告（188 页）
FastMoss：2024 年度 TikTok 生态发展白皮书（122 页）
Check Point：2025 年网络安全报告 - 主要威胁、新兴趋势和 CISO 建议（57 页）
【AAAI2025 教程】评估大型语言模型：挑战与方法，199 页 ppt
《21 世纪美国的主导地位：核聚变》最新报告
沃尔特基金会（Volta Foundation）：2024 年全球电池行业年度报告（518 页）
国际科学理事会：2025 为人工智能做好国家研究生态系统的准备 - 2025 年战略与进展报告（英文版）（118 页）
光子盒：2025 全球量子计算产业发展展望报告（184 页）
奥纬论坛：2025 塑造未来的城市研究报告：全球 1500 个城市的商业吸引力指数排名（124 页）
Future Matters：2024 新兴技术与经济韧性：日本未来发展路径前瞻报告（17 页）
《人类与人工智能协作的科学与艺术》284 页博士论文
《论多智能体决策的复杂性：从博弈学习到部分监控》115 页
《2025 年技术展望》56 页 slides
大语言模型在多智能体自动驾驶系统中的应用：近期进展综述
【牛津大学博士论文】不确定性量化与因果考量在非策略决策制定中的应用
皮尤研究中心：2024 美国民众对气候变化及应对政策的态度调研报告：气候政策对美国经济影响的多元观点审视（28 页）
空间计算行业深度：发展趋势、关键技术、行业应用及相关公司深度梳理 - 250224（33 页）
Gartner：2025 网络安全中的 AI：明确战略方向研究报告（16 页）
北京大学：2025 年 DeepSeek 系列报告 - 提示词工程和落地场景（86 页）
北京大学：2025 年 DeepSeek 系列报告 - DeepSeek 与 AIGC 应用（99 页）
CIC 工信安全：2024 全球人工智能立法的主要模式、各国实践及发展趋势研究报告（42 页）
中科闻歌：2025 年人工智能技术发展与应用探索报告（61 页）
AGI 智能时代：2025 年 Grok - 3 大模型：技术突破与未来展望报告（28 页）
上下滑动查看更多
来源：人工智能学家