Effective Strong Dimension, Algorithmic Information, and Computational Complexity
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
复制标题
有效强维度、算法信息和计算复杂度
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Elvira Mayordomo
中科院分区：
文献类型：
--
作者：
K. Athreya;J. M. Hitchcock;J. H. Lutz;Elvira Mayordomo
分形维的两个最重要的概念是由Hausdorff(1919)提出的{it Hausdorff维}和由Tricot(1982)提出的{it填充维}。
Lutz(2000)最近证明了Hausdorff维的一个简单的刻画：{it gales}，这是一种推广了鞅的投注策略。对这些大风施加各种可计算性和复杂性约束，产生了一系列有效的Hausdorff维度。
在本文中，我们证明了堆积尺寸也可以用大风来刻画。此外，尽管通常的填充维度的定义比Hausdorff维度的定义复杂得多，但我们对填充维度的大风刻画是Hausdorff维度的大风刻画的精确对偶--而且非常简单。
有效地刻画了包装尺寸的大风，产生了各种{it有效强维}，它们是上述有效尺寸的精确对偶。
我们发展了有效强维的基本性质，并证明了一些与随机性、Kolmogorov复杂性、预测、布尔电路大小复杂性、多项式时间阶数和数据压缩等基本方面相关的结果。
The two most important notions of fractal dimension are {it Hausdorff dimension}, developed by Hausdorff (1919), and {it packing dimension}, developed by Tricot (1982).
Lutz (2000) has recently proven a simple characterization of Hausdorff dimension in terms of {it gales}, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension.
In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of -- and every bit as simple as -- the gale characterization of Hausdorff dimension.
Effectivizing our gale characterization of packing dimension produces a variety of {it effective strong dimensions}, which are exact duals of the effective dimensions mentioned above.
We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression.