Dimension in complexity classes
Dimension in complexity classes
复制标题
复杂性类别中的维度
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. H. Lutz
中科院分区：
文献类型：
--
作者：
J. H. Lutz
利用大风发展了资源有限维度理论，大风是马丁-大风的自然推广。当资源边界/SPL Delta/(该理论的一个参数)不受限制时，所得到的维度正好是经典的Haludolff维度(有时称为“分形维”)。参数/SPL Delta/的其他选择在E、E/sub2/、esspace和其他复杂类中以及在所有可判定问题的类中产生内维理论。一般来说，如果C是这样一个类，那么每个语言集合X在C中都有一个维度，它是实数dim(X|C)/SPL ISIN/[0，1]。1.对于每个实数0/SPL LE//SPLα//SPL LES/1/2，由渐近包含至多/SPLα/的所有语言组成的集合FREQ(/SPL AP//SPLα/)具有维度/SPL Hscr/(/SPLα/)-E和E/sub2/中的/SPLα/-的二进制熵。2.对于每个实数0/SPL LE//SPLα//SPL LES/1，集合大小(/SPLα/2/sup n//n)由至多/SPLα/2/sup n//n个门的布尔电路可判定的所有语言组成，在空间中具有维度/splα/1。
A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martin-gales. When the resource bound /spl Delta/(a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Haludolff dimension (sometimes called "fractal dimension"). Other choices of the parameter /spl Delta/ yield internal dimension theories in E, E/sub 2/, ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if C is such a class, then every set X of languages has a dimension in C, which is a real number dim(X|C)/spl isin/[0, 1]. Along with the elements of this theory two preliminary applications are presented: 1. For every real number 0/spl les//spl alpha//spl les/ 1/2 , the set FREQ(/spl ap//spl alpha/), consisting of all languages that asymptotically contain at most /spl alpha/ of all strings, has dimension /spl Hscr/(/spl alpha/)-the binary entropy of /spl alpha/-in E and in E/sub 2/. 2. For every real number 0/spl les//spl alpha//spl les/1, the set SIZE(/spl alpha/2/sup n//n), consisting of all languages decidable by Boolean circuits of at most /spl alpha/2/sup n//n gates, has dimension /spl alpha/ in ESPACE.