Dimension, entropy rates, and compression

作     者：Hitchcock, John M. Vinodchandran, N. V. 

作者机构：Univ Wyoming Dept Comp Sci Laramie WY 82071 USA Univ Nebraska Dept Comp Sci & Engn Lincoln NE 68588 USA 

出 版 物：《JOURNAL OF COMPUTER AND SYSTEM SCIENCES》 (计算机与系统科学杂志)

年 卷 期：2006年第72卷第4期

页      面：760-782页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：University of Nebraska National Science Foundation, NSF, (CCF-0430991) Directorate for Computer and Information Science and Engineering, CISE, (0430991, 0515313) 

主　　题：resource-bounded dimension scaled dimension Hausdorff dimension gales circuit complexity Kolmogorov complexity computational complexity 

摘      要：This paper develops new relationships between resource-bounded dimension, entropy rates, and compression. New tools for calculating dimensions are given and used to improve previous results about circuit-size complexity classes. Approximate counting of SpanP functions is used to prove that the NP-entropy rate is an upper bound for dimension in Delta(E)(3), the third level of the exponential-time hierarchy. This general result is applied to simultaneously improve the results of Mayordomo [E. Mayordomo, Contributions to the study of resource-bounded measure, PhD thesis, Universitat Politecnica de Catalunya, 1994] on the measure on P/poly in Delta(E)(3) and of Lutz [J.H. Lutz, Dimension in complexity classes, SIAM J. Comput. 32 (5) (2003) 1236-1259] on the dimension of exponential-size circuit complexity classes in ESPACE. Entropy rates of efficiently rankable sets, sets that are optimally compressible, are studied in conjunction with time-bounded dimension. It is shown that rankable entropy rates give upper bounds for time-bounded dimensions. We use this to improve results of Lutz [J.H. Lutz, Almost everywhere high nonuniform complexity, J. Comput. System Sci. 44 (2) (1992) 220-258] about polynomial-size circuit complexity classes from resource-bounded measure to dimension. Exact characterizations of the effective dimensions in terms of Kolmogorov complexity rates at the polynomial-space and higher levels have been established, but in the time-bounded setting no such equivalence is known. We introduce the concept of polynomial-time superranking as an extension of ranking. We show that superranking provides an equivalent definition of polynomial-time dimension. From this superranking characterization we show that polynomial-time Kolmogorov complexity rates give a lower bound on polynomial-time dimension. (C) 2005 Elsevier Inc. All rights reserved.