OpenAI 问题 #109 再收紧：κ 改进约 5.7 亿倍，逼近理论上限

aran_nayebi · x · 2026-10-07

0xdoug 团队发布对 OpenAI Problem #109（整数乘法）的进一步收紧：在 OpenAI 算法接口条件下，将 T(n)=O(n(log n)^(1−κ)) 中的指数节省参数 κ 从 2⁻¹⁸² 提升至约 2⁻⁷⁸ 量级，相比此前结果约 5.7 亿倍改进，较 OpenAI 原始结果改进 2¹⁰⁴ 倍。关键技巧是使用非相邻轴交换（nonadjacent axis swaps）绕开网络中的三次方瓶颈，把布局路由从 O(d²) 次交换降到 O(d)。作者指出新见证（witness）按二次方扩展，原三次方瓶颈处的上限不再适用，尚未确立新上限。