CaltechAUTHORS
  A Caltech Library Service

Resource-Bounded Category and Measure in Exponential Complexity Classes

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

[img]
Preview
Postscript
See Usage Policy.

3518Kb
[img]
Preview
Other (Adobe PDF (3MB))
See Usage Policy.

3174Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1987.5243-tr-87

Abstract

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
Record Number:CaltechCSTR:1987.5243-tr-87
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1987.5243-tr-87
Usage Policy:You are granted permission for individual, educational, research and non-commercial 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