引用theemathas · 2017-01
“The catch is that the constants in the big-O are enormous.”
指出这个算法的 big-O 常数大得惊人
渐近最优地求解任何良定义问题、但常数巨大的算法
描述一个算法 M,求解任何良定义问题 p 的速度与解 p 的最快算法一样,只差一个因子 5 和低阶加性项。M 在执行可证明正确的求解程序与枚举所有证明(包括程序正确性证明和运行时间上界证明)之间最优地分配资源,通过忽略没有正确性证明的程序来避开 Blum 加速定理。论文还利用柯尔莫哥洛夫复杂度的扩展和两个新的函数复杂度度量,说明计算某函数的最高效程序也属于可证明地计算该函数的最短程序之列。
评论者指出它的代价是大 O 里的常数大得惊人,称它是对渐近分析的一次妙趣横生的归谬。
这条路径先读通用搜索与 Solomonoff 式先验的背景,再读 Hutter 的通用人工智能理论,最后读本文的最快最短算法。
里面用到 Levin 搜索与 Solomonoff 先验,这是本文要改进的通用搜索思路的背景。
读Levin 搜索与按程序长度和运行时间分配先验的基本想法;不必深入物理部分。
同一作者关于通用智能的理论,使用同样的算法信息论基础。
读Solomonoff 归纳的概念以及它与决策论结合成 AIXI 的结构。
目标论文:渐近最优地求解任何良定义问题的算法。
读算法 M 如何在程序运行与证明枚举之间分配时间,以及巨大的加性常数与实际含义。
“The catch is that the constants in the big-O are enormous.”
“Basically this is a delightful reductio of asymptotic analysis”