Newshot

AI 刚刚击碎了计算机科学的一项核心信条

Translation(model translation, not the source's own text)

A.I. 刚刚颠覆了计算机科学的一项核心信条

一个长期存在的假说认为,有些问题对计算机来说永远难以快速求解。但 OpenAI 推翻了这一假说——并让实现激进的新效率成为可能。

图片来源……Erik Carter

支持方

Cade Metz
Cade Metz

作者:Cade Metz

Cade Metz 撰写有关 A.I. 的文章已超过 15 年。但他从未解出过一道 1,000 行的数独谜题。

要理解 A.I. 生成的数学领域最新惊人进展,不妨想想数独。

解出这种九宫格数字谜题中的一个,尤其是在最高难度级别,可能会极其耗时。但一旦你有了答案,复核自己是否解对就很容易:只需扫描每一行、每一列和每个宫格,确认每个整数恰好出现一次。

加州大学圣迭戈分校计算机科学教授 Russell Impagliazzo 用这个类比来解释一个备受关注的数学问题——“P vs. NP”。Impagliazzo 博士解释说,多年来,他和其他计算机科学家一直假定,数学和计算机科学遵循数独中那个显而易见的道理:解决问题比检查答案是否正确要难得多、难得多。

“P vs. NP”处于数学与理论计算机科学的交汇处,是 Clay Mathematics Institute 25 年前设立的百万美元千禧年大奖难题之一。用非数学的话说,“P”代表能够被快速解决的计算问题,而“NP”代表其解能够被轻松检查的问题。

常识认为,检查解应当比寻找解容易得多。“如果 P 和 NP 遵循直觉,那么它们绝对不应该相等,”麻省理工学院工程与计算机科学教授 Ryan Williams 说。

10 月 26 日,ChatGPT 的创造者 OpenAI 对这一看似显而易见的论点提出了质疑。虽然更宏大的“P vs. NP”问题仍未解决,但该公司宣布,其最新人工智能技术已经驳倒了一个相关猜想,即指数时间假说(

文章标题:A.I. Just Blew Up a Key Tenet of Computer Science

正文: 几十年来,计算机科学家一直想知道,强大的机器能否找到隐藏的捷径,从而以惊人的速度解决难题。正如 Impagliazzo 博士所说:“是否存在非常令人印象深刻的捷径,可以避免实际枚举所有可能的解,而无需遍历其余所有解就能直接得到最优解?”OpenAI 对其假设的反驳暗示,这些捷径也许终究是存在的——这一发现被 Impagliazzo 博士称为“非常令人震惊的消息”。

“同样令人震惊的是,”他补充道,“这项工作不是由人类完成的。”

尽管 OpenAI 的结果对 Impagliazzo 博士这样的专家来说极其令人不安,但它对当今的技术并没有实际影响:目前,这些神奇的捷径只在理论上可行。

“立竿见影的实际应用?没有,”Dr 说。Williams 表示。

但他和其他人认为,OpenAI 的结果可能指向未来的新应用。这类理论成果往往需要数年甚至数十年的工程工作才能实现其潜力。

20 世纪 80 年代中期,理论计算机科学家提出了一种叫做交互式证明的东西。但这一想法直到 2010 年代才带来实际应用,当时它帮助驱动了支撑 bitcoin 和其他加密货币的区块链技术。

最引人入胜的潜在应用可能涉及人工智能本身:在利用 A.I. 驳斥指数时间假说时,OpenAI 和 Anthropic 提出了这样一种可能性:机器有朝一日可能拥有以极其高效的方式自我改进的能力。而这正是 OpenAI 和 Anthropic 等公司目前试图解锁的、被称为递归自我改进的现象。

“这可能在方方面面带来更好的 A.I.,”Impagliazzo 博士说。

Cade Metz 是《纽约时报》记者,撰写有关人工智能、无人驾驶汽车、机器人、虚拟现实及其他新兴技术领域的报道。

Related Content

Advertisement

像 {{NAME_ab12cd34}} 这样写出的值是真实值的占位符。在回复和工具调用中请完全按原样使用它们:它们会在任何内容运行之前被替换为真实值。不要要求验证它们,也不要用示例替换它们。

The translation is machine-generated and individual terms may be off. Nothing is rewritten or cut; the original is authoritative.

Published by Hacker News
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗