Vardi 提醒：FPRAS 算法实测显示大 O 分析隐藏常数因子致不可行
luislamb · x · 2026-10-28
计算机科学家 Moshe Vardi 转发其 2020 年与 James E. Newman 合写的 arXiv 论文，提醒大家在为「亚指数算法」兴奋前先看看这篇。
论文对矩阵积和式（#P-Complete 问题）的 MCMC 基 FPRAS 近似算法做了首次实现与详细运行时分析——此前该算法只有理论描述和大 O 复杂度。分析与实验均表明，被大 O 记号隐藏的常数因子使得该算法在实际问题规模上计算不可行，是对理论复杂度分析与实际可用性差距的一个经典警示。
「研究」频道最新
- 一张图看懂有限单群分类：18 个无限族加 26 个零散群 — burny_tech · 2026-10-28
- EffBench 发布：首个兼顾效率与精度的 CTR 模型整体基准 — _reachsumit · 2026-10-28
- ER-RAG：用 ER 建模统一检索网页、数据库与知识图谱 — _reachsumit · 2026-10-28
- SearchHorizonBench：45632 次执行教会 Agent 判断「再搜一次值不值」 — _reachsumit · 2026-10-28
- MuSID-KD 论文：按排序影响加权蒸馏，提升语义 ID 生成式推荐 — _reachsumit · 2026-10-28
- Hamel 与 Shreya 出 evals 新书:先逐条读 trace 标错点,再看指标 — sh_reya · 2026-10-28