Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1, 1987 | public
Report Open

Resource-Bounded Category and Measure in Exponential Complexity Classes

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

5243_TR_87.pdf
Files (6.9 MB)
Name Size Download all
md5:9fc27a51c684a79a1f664761df8fa5a5
3.3 MB Preview Download
md5:2ec7b133902f8fce50576bca74519bfb
3.6 MB Download

Additional details

Created:
August 19, 2023
Modified:
December 22, 2023