标签
doubleAI 声称以 2000 美元的成本解决了图论中长期未解的最长路径问题，该成果在量子计算机的错误纠正和加速计算方面具有潜在的实际应用价值。
一篇技术评论文章，批评 OpenAI 在数学论文集中声称的更快快速傅里叶变换（FFT）算法，指出其改进微乎其微，更像是利用理论模型在硬件上并不实际可行的"恶意利用"，而非真正的突破。
一次自动化研究运行，探索复杂度低于 n log n 的整数乘法算法，提供可复现的贡献成果、代码仓库贡献指南，以及对研究思路和拉取请求的交互式可视化。
This paper analyzes reasoning shortcuts in neurosymbolic systems through symmetry and automorphism groups, reveals flaws in a prior framework, proves complexity-theoretic results, and empirically validates the corrected theory on benchmarks like CLE4EVR and rsbench.
本文研究先修DAG上的教学排序，证明随机学习动态可以精确归约为确定性最短路径问题，然而最优排序在一般情况下仍是NP难的，在受限的迁移结构下存在多项式时间情形。
一位中国教授发现了一种新的确定性最短路径算法，通过结合Dijkstra和Bellman-Ford算法并引入前沿缩减，突破了40年来的排序障碍，在稀疏图上实现了O(m log^(2/3) n)的时间复杂度。
本文宣布了Tim Roughgarden开设的一门免费在线课程，涵盖计算机科学的基本概念，包括图灵机、停机问题、算法效率、NP完全性以及P与NP问题。
本文建立了市场竞争性与P与NP问题之间的理论联系，论证了竞争性市场存在的条件是且仅是P ≠ NP。
计算复杂性理论家认为，半经典引力中的非线性动力学将使得不可想象的强大计算成为可能，从而证明引力必须量子化。该论文利用薛定谔-牛顿方程表明，经典引力与量子物质耦合会导致计算矛盾。
本文论证在半经典引力下，一个大规模的量子比特可以通过非线性动力学在多项式时间内解决NP完全问题，这暗示引力必须被量子化。
一条社交媒体帖子，通过将 NP 比作总是能找到正确路径的“神奇计算机”来解释 P 与 NP 问题，并引用了 MIT 的《算法导论》课程。
# 鲁棒分类中的计算限制与双赢结果 来源: [https://openai.com/index/computational-limitations-in-robust-classification-and-win-win-results/](https://openai.com/index/computational-limitations-in-robust-classification-and-win-win-results/) ## 摘要 我们延续关于学习鲁棒分类器中统计/计算权衡的研究,跟进 Bubeck, Lee, Price 和 Razenshteyn 的最近工作,他们展示了分类任务的示例,其中 \(a