算法最优的外部测度

《ACM Transactions on Computation Theory》：Algorithmically Optimal Outer Measures

算法分形维数与经典局部分形维数的关系研究，提出全局和局部最优条件，证明存在全局最优外测度，并利用Kolmogorov复杂性定义的κ外测度证明两者等价性，讨论点集原理影响。

　　

摘要

我们研究了欧几里得空间中算法生成的分形维数与经典局部分形维数之间的关系。我们提出了下半可计算外测度的全局和局部最优性条件，并证明了全局最优外测度的存在性。我们的主要定理指出，任何局部最优外测度的经典局部分形维数与其算法生成的分形维数完全一致。我们的证明使用了一种特别方便的局部最优外测度 κ，该测度是根据柯尔莫哥洛夫复杂性来定义的。我们还讨论了这一点对点集原理的影响。