Resource-Bounded Category and Measure in Exponential Complexity Classes
- Creators
- Lutz, Jack H.
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.
Files
Name | Size | Download all |
---|---|---|
md5:9fc27a51c684a79a1f664761df8fa5a5
|
3.3 MB | Preview Download |
md5:2ec7b133902f8fce50576bca74519bfb
|
3.6 MB | Download |
Additional details
- Eprint ID
- 26938
- Resolver ID
- CaltechCSTR:1987.5243-tr-87
- Created
-
2002-07-24Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Computer Science Technical Reports