
要理解人工智能在数学领域的最新突破,不妨从数独说起。破解高难度数独往往耗时费力,但验证答案是否正确却轻而易举:只需检查行列与宫格,确认数字无重复即可。
加州大学圣地亚哥分校计算机科学教授拉塞尔·安帕利亚佐(Russell Impagliazzo)借此阐释著名的“P vs NP”难题。多年来,学界普遍假设数学与计算机科学遵循这一常识:求解问题的难度远高于验证答案。
作为克莱数学研究所千禧年大奖难题之一,“P vs NP”位于数学与理论计算机科学的交叉点。通俗而言,“P”代表可快速求解的问题,“NP”则指解易于验证的问题。麻省理工学院教授瑞安·威廉姆斯(Ryan Williams)指出,若符合直觉,P与NP绝不应相等。
10月26日,OpenAI对这一看似显而易见的论点发起挑战。尽管“P vs NP”核心问题仍未解决,但该公司宣布,其最新AI技术推翻了相关的“指数时间假设”(ETH)。
ETH由安帕利亚佐博士于1998年与同事拉马莫汉·帕图里及贝尔实验室研究员弗朗西斯·赞恩共同提出。该假设认为,对于计算机而言,某些问题始终难以快速求解。OpenAI的这一发现,直接动摇了这一长期存在的理论基石。