Citation
Lutz, Jack Harold (1987) ResourceBounded Category and Measure in Exponential Complexity Classes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/dccw3z56. https://resolver.caltech.edu/CaltechTHESIS:03192012101000956
Abstract
This thesis presents resourcebounded category and resource boundedmeasure  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 certain twoperson infinite games called resourcebounded BanachMazur 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 ∩ 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 in ESPACE have high spacebounded Kolmogorov complexity.
These tools are also combined with a new hierarchy of exponential time complexity classes to refine known relationships between nonuniform complexity and time complexity.
In the last part of the thesis, known properties of hard languages are extended. In particular, recent results of Schöning and Huynh state that any language L which is ≤^{P}_{m}hard for E or ≤^{P}_{T}hard for ESPACE cannot be feasibly approximated (i.e., its symmetric difference with any feasible language has exponential density). It is proven here that this conclusion in fact holds unless only a meager subset of E is ≤^{P}_{m}reducible to L and only a meager, measure 0 subset of ESPACE is ≤^{PSPACE}_{m}reducible to L. (It is conjectured, but not proven, that this result is actually stronger than those of Schöning and Huynh.) This suggests a new lower bound method which may be useful in interesting cases.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  Mathematics; Computer Science  
Degree Grantor:  California Institute of Technology  
Division:  Physics, Mathematics and Astronomy  
Major Option:  Mathematics  
Minor Option:  Computer Science  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Thesis Committee: 
 
Defense Date:  18 May 1987  
Funders: 
 
Record Number:  CaltechTHESIS:03192012101000956  
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:03192012101000956  
DOI:  10.7907/dccw3z56  
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  6854  
Collection:  CaltechTHESIS  
Deposited By:  Ben Perez  
Deposited On:  19 Mar 2012 18:50  
Last Modified:  16 Apr 2021 22:58 
Thesis Files

PDF
 Final Version
See Usage Policy. 10MB 
Repository Staff Only: item control page