Resource-bounded measure was introduced by Lutz as a quantitative approach to the study of complexity classes. Lutz takes two main classes, exponential time, denoted E, and exponential space, denoted ESPACE, as comparison patterns, and, for each class X, tries to establish a size comparison between "X intersection E" and E, or between "X intersection ESPACE" and ESPACE.
The main objectives of this theory are the following:
- Extension of existence results of the form "there is a language in class C that is not in class X", to abundance results of the form "most languages in C are not in X", formally expressed as "X has measure 0 in C". The interest of an abundance result is that it shows the typical behaviour of languages in a class, and therefore is more informative than an existence result that could as well correspond to an exception in the class.
- Use of resource-bounded measure as a probabilistic method for complexity classes. In order to prove that there exists a language in C with property Pi, it may be easier to prove that the class of languages with property Pi does not have measure 0 in C, since measure techniques that prove abundance are often more powerful than constructive proofs.
- Use of resource-bounded measure as a formal tool in Structural Complexity for the construction of new working hypothesis, characterization of complexity classes, definition of new concepts, etc.
In this dissertation we study in deep resource-bounded measure, its possible generalizations to other complexity classes and its applications in the three exposed ways, namely the extension from existence to abundance results, the probabilistic method, and the identification of useful Structural Complexity hypothesis.
In chapter 2 we study the extension of resource-bounded measure to the class PSPACE. We prove that the natural candidate of measure in PSPACE is not valid unless the unlikely consequence of E being included in PSPACE holds. We then propose a valid definition based on on-line computable functions, and use it to prove that a class of self-reducible languages has measure 0 in PSPACE.
In chapter 3 we show that that almost every language in E is P-bi-immune. This abundance result extends the existence one of Bertman and Hartmanis. We then use this result to show that measure and category are incomparable in the resource-bounded setting.
In chapter 4 we prove that the class of sets that can be reduced with a sublinear number of queries to a non-dense set has measure 0 in E, that is, almost every language in E is not in the cited class. Applying the probabilistic method, this shows that E does not have non-dense sublinear-tt-hard languages, extending the best known results on the density of hard languages for E.
In chapter 5 we study the consequences of the unproven hypothesis "NP does not have measure 0 in E". For example, under this hypothesis we show that there is a language that is Turing-complete but not many-one-complete, for NP. This conclusion, widely believed to be true, is not known to follow from "P not equal to NP" or other traditional complexity-theoretic hypotheses.
Table of contents:
1 Introduction and preliminaries 1.1 Introduction 1.2 Main contributions 1.3 Preliminaries 1.4 Resource-bounded measure 1.5 Some technical lemmas 1.6 gamma-measurability and the Kolmogorov 0-1 law 2 Measuring in PSPACE 2.1 Introduction 2.2 Measure in PSPACE 2.3 gamma-additivity in PSPACE 3 Measure versus category: the P-bi-immune sets 3.1 Introduction 3.2 P-bi-immunity and resource-bounded measure 3.3 P-bi-immunity and resource-bounded category 4 Measure of nonuniform complexity classes 4.1 Introduction 4.2 Advice complexity classes 4.3 Weak-stochasticity 4.4 Measure of Ptt(nonDense) with sublinear number of queries 4.5 P/poly inside the Exponential Hierarchy 5 If NP is not small 5.1 Introduction 5.2 If NP does not have p-measure 0 5.3 Separating completeness notions in NP 5.4 Separating reducibilities in NP 5.5 Further results and open problems 6 Cones 6.1 Introduction 6.2 Weakly-useful languages 6.3 On the robustness of ALMOST-R 6.4 Bidimensional measure References
