OpenAI 论文称离散傅里叶变换可突破 O(n log n)

OpenAI 近期发布论文称，存在一种算法可在 O(n(log n)^(1−ε)) 时间内计算离散傅里叶变换，其中 ε = 10^−13。这一结果略微打破了此前被认为最优的 O(n log n) 复杂度，但目前在实践上毫无价值。作者认为，既然定理证明原有假设存在偏差，这一 ε 缺口或许会继续扩大。