Lutz, Jack H. (1987) Resource-Bounded Category and Measure in Exponential Complexity Classes. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1987.5243-tr-87
See Usage Policy.
Other (Adobe PDF (3MB))
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1987.5243-tr-87
This thesis presents resource-bounded category and resource- bounded measure - two new tools for computational complexity theory - and some applications of these tools to the structure theory of exponential complexity classes. Resource-bounded category, a complexity-theoretic version of the classical Baire category method, identifies certain subsets of PSPACE, E, ESPACE, and other complexity classes as meager. These meager sets are shown to form a nontrivial ideal of "small" subsets of the complexity class. The meager sets are also (almost) characterized in terms of curtain two-person infinite games called resource-bounded Banach-Maxur games. Similarly, resource-bounded measure, a complexity-theoretic version of Lebesgue measure theory, identifies the measure 0 subsets of E, ESPACE, and other complexity classes, and these too are shown to form nontrivial ideals of "small" subsets. A resource-bounded extension of the classical Kolmogorov zero-one law is also proven. This shows that measurable sets of complexity-theoretic interest either have measure 0 or are the complements of sets of measure 0. Resource-bounded category and measure are then applied to the investigation of uniform versus nonuniform complexity. In particular, Kannan's theorem that ESPACE P/Poly is extended by showing that P/Poly fl ESPACE is only a meager, measure 0 subset of ESPACE. A theorem of Huynh is extended similarly by showing that all but a meager, measure 0 subset of the languages i n ESPACE have high space-bounded Kolmogorov complexity.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Computer Science Technical Reports|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechCSTR|
|Deposited On:||24 Jul 2002|
|Last Modified:||26 Dec 2012 14:10|
Repository Staff Only: item control page