Lutz, Jack H. (1987) ResourceBounded Category and Measure in Exponential Complexity Classes. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1987.5243tr87

Postscript
See Usage Policy. 3518Kb  

Other (Adobe PDF (3MB))
See Usage Policy. 3174Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1987.5243tr87
Abstract
This thesis presents resourcebounded 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. Resourcebounded category, a complexitytheoretic 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 twoperson infinite games called resourcebounded BanachMaxur games. Similarly, resourcebounded measure, a complexitytheoretic 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 resourcebounded extension of the classical Kolmogorov zeroone law is also proven. This shows that measurable sets of complexitytheoretic interest either have measure 0 or are the complements of sets of measure 0. Resourcebounded 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 spacebounded Kolmogorov complexity.
Item Type:  Report or Paper (Technical Report) 

Group:  Computer Science Technical Reports 
Record Number:  CaltechCSTR:1987.5243tr87 
Persistent URL:  http://resolver.caltech.edu/CaltechCSTR:1987.5243tr87 
Usage Policy:  You are granted permission for individual, educational, research and noncommercial reproduction, distribution, display and performance of this work in any format. 
ID Code:  26938 
Collection:  CaltechCSTR 
Deposited By:  Imported from CaltechCSTR 
Deposited On:  24 Jul 2002 
Last Modified:  26 Dec 2012 14:10 
Repository Staff Only: item control page