OpenAI 说它证明了「不可能」:3-SAT 的亚指数算法,与被撼动的指数时间假设——Two Minute Papers
Two Minute Papers 主理人 Károly Zsolnai-Fehér 用猫、狗、机器人的三行逻辑题在三分钟内讲清 3-SAT 与指数时间假设(ETH):三十年来被视为计算世界「物理定律」的这堵墙,如今被 OpenAI 的一篇论文声称推倒——为 3-SAT 给出亚指数上界,且论文不只给证明、还给出算法本身并能精确数出解的个数。Károly 的态度罕见地重:「我原以为这不会发生在我的有生之年。」他同时给出两条清醒限定:专家评审尚未百分之百完成;这不是 P versus NP 被解决。送药路线、频率分配、传感器布点、航天器装载为何与猫狗机器人题同构,看 Karp 归约一节。