按年被提到
20022019 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:cs/0206022 · cs.CC

The Fastest and Shortest Algorithm for All Well-Defined Problems

适用于所有良定义问题的最快最短算法
Marcus Hutter · 2002

渐近最优地求解任何良定义问题、但常数巨大的算法

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2017-01-30 · 最近 2022-08-28
4不同的人
4活跃月份
4讨论串
0被引(OpenAlex)

描述一个算法 M,求解任何良定义问题 p 的速度与解 p 的最快算法一样,只差一个因子 5 和低阶加性项。M 在执行可证明正确的求解程序与枚举所有证明(包括程序正确性证明和运行时间上界证明)之间最优地分配资源,通过忽略没有正确性证明的程序来避开 Blum 加速定理。论文还利用柯尔莫哥洛夫复杂度的扩展和两个新的函数复杂度度量,说明计算某函数的最高效程序也属于可证明地计算该函数的最短程序之列。

HN 为什么提它

评论者指出它的代价是大 O 里的常数大得惊人,称它是对渐近分析的一次妙趣横生的归谬。

方法难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1算法复杂度与渐近分析(big-O)
2柯尔莫哥洛夫复杂度(Kolmogorov complexity)
3Levin 通用搜索
4形式证明系统与可计算性理论

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

这条路径先读通用搜索与 Solomonoff 式先验的背景,再读 Hutter 的通用人工智能理论,最后读本文的最快最短算法。

  1. 1
    Algorithmic Theories of Everything算法式万物理论 · 2000

    里面用到 Levin 搜索与 Solomonoff 先验,这是本文要改进的通用搜索思路的背景。

    读Levin 搜索与按程序长度和运行时间分配先验的基本想法;不必深入物理部分。

  2. 2
    A Theory of Universal Artificial Intelligence based on Algorithmic Complexity基于算法复杂度的通用人工智能理论 · 2000

    同一作者关于通用智能的理论,使用同样的算法信息论基础。

    读Solomonoff 归纳的概念以及它与决策论结合成 AIXI 的结构。

  3. 3
    The Fastest and Shortest Algorithm for All Well-Defined Problems适用于所有良定义问题的最快最短算法 · 2002 · 就是这篇

    目标论文:渐近最优地求解任何良定义问题的算法。

    读算法 M 如何在程序运行与证明枚举之间分配时间,以及巨大的加性常数与实际含义。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用theemathas · 2017-01

“The catch is that the constants in the big-O are enormous.”

指出这个算法的 big-O 常数大得惊人
Ask HN: What are your favorite algorithms?原评论 ↗
引用voidmain · 2019-06

“Basically this is a delightful reductio of asymptotic analysis”

称它是对渐近分析的绝妙归谬
Galactic Algorithms (2010)原评论 ↗
被提交为 story · 2 次