The topic of this thesis is the study of randomness concepts and their applications in computational complexity theory. In Chapter 1, we discuss the classical notions of randomness. We give a systematic study of various notions of randomness, especially, of the following concepts defined in terms of typicalness: Martin-L\"{o}f randomness, Lutz randomness, Schnorr randomness, Ko randomness, and Kurtz randomness. We study each notion of typicalness by using three different approaches: the approach based on constructive null covers, the approach based on martingales and the approach based on Solovay style criteria (the first Borel-Cantelli lemma-like condition).
Schnorr has shown that Martin-L\"{o}f randomness is a proper refinement of Lutz randomness, but his proof was not correct, and he left open the question whether Lutz randomness is a proper refinement of Schnorr randomness. In the sequel, the later was conjectured to be true by van Lambalgen and Lutz. We prove this conjecture and we correct the proof of Schnorr's result, thereby completely clarifying the relations among the above cited important randomness concepts. At the same time, we will show that there is a Schnorr random sequence which is not Church stochastic.
In Chapter 4, we extend Kurtz recursion theoretic notion of $n$-randomness to the recursion theoretic notions of Lutz and Schnorr $n$-randomness.
Notions of resource bounded randomness have been introduced by several authors. Though it was known that most of these notions are different, the relations among them were not fully understood. In Chapter 5, we give a survey of these notions and show their relations to each other. Moreover, we introduce several new notions of resource bounded randomness corresponding to the classical notions of randomness discussed in Chapter 3. We show that the notion of polynomial time bounded Ko randomness is independent of the notions of polynomial time bounded Lutz, Schnorr and Kurtz randomness. Lutz has conjectured that, for a given time or space bound, the corresponding resource bounded Lutz randomness is a proper refinement of resource bounded Schnorr randomness. We answer this conjecture affirmatively. Moreover, we show that resource bounded Schnorr randomness is a proper refinement of resource bounded Kurtz randomness too. In contrast to this result, however, we also show that the notions of polynomial time bounded Lutz, Schnorr and Kurtz randomness coincide in the case of recursive sets, whence it suffices to study the notion of resource bounded Lutz randomness in the context of complexity theory.
The stochastic properties of resource bounded random sequences (i.e., resource bounded typical sequences) will be discussed in detail. Schnorr has already shown that the law of large numbers holds for $p$-random sequences. We show that another important law in probability theory, the law of the iterated logarithm, holds for $p$-random sequences too. (In fact, we can show that all the standard laws (e.g., the $\alpha\ln n$-gap law for $\alpha <1$) in probability theory which only depend on the $0$-$1$ distributions within the sequences hold for $p$-random sequences.) Hence almost all sets in the exponential time complexity class are ``hard" from the viewpoint of statistics. These laws also give a quantitative characterization of the density of $p$-random sets. And, when combined with an invariance property of $p$-random sets, these laws are useful in proving that some classes of sets have $p$-measure $0$.
Polynomial time safe and unsafe approximations for intractable sets were introduced by Meyer, Paterson, Yesha, Duris, Rolim and Ambos-Spies, respectively. The question of which sets have optimal safe and unsafe approximations has been investigated extensively. Recently, Duris, Rolim and Ambos-Spies showed that the existence of optimal polynomial time approximations for the safe and unsafe cases is independent. Using the law of the iterated logarithm for $p$-random sequences discussed in Chapter \ref{chapter5}, we extend this observation by showing that both the class of $\Delta$-levelable sets and the class of sets which have optimal polynomial time unsafe approximations have $p$-measure $0$. Hence $p$-random sets do not have optimal polynomial time unsafe approximations. We will also show the relations between resource bounded genericity concepts (introduced by Ambos-Spies et al., Fenner and Lutz) and the polynomial time safe (unsafe) approximation concept.
In the last chapter, we show that no {\bf P}-selective set is $\le_{tt}^p$-hard for ${\bf NP}$ unless ${\bf NP}$ is small.
Table of Contents
1. Introduction and Notation .........................................1
1.1 Introduction .................................................1
1.2 Summary of Main Contributions ..................... ..........5
1.3 Notation......................................................6
2. Basics of Lebesgue Measure Theory .............. .................9
2.1 Lebesgue Measure Theory ......................................9
2.2 Martingales ................................................ 11
3. A Comparison of Classical Randomness Concepts ....................13
3.1 Typicalness .................................................13
3.2 Relations among Notions of Typicalness.......................28
3.3 Chaoticness and Stochasticity................................35
3.4 Invariance Properties of Typical Sequences...................37
4. $n$-Randomness....................................................43
4.1 Different Kinds of $n$-Randomness............................43
4.2 Relations among Notions of $n$-Randomness....................46
5. Resource Bounded Randomness.......................................49
5.1 Resource Bounded Typicalness.................................50
5.2 Resource Bounded Stochasticity and the Law of Large Numbers..58
5.3 The Law of the Iterated Logarithm for $p$-Random Sequences...65
5.4 Some Remarks on Statistical Laws.............................74
6. Resource Bounded Category, Resource Bounded Measure and Polynomial
Time Approximations ..............................................75
6.1 Genericity versus Polynomial Time Safe Approximation.........77
6.2 Genericity versus Polynomial Time Unsafe Approximations......81
6.3 Resource Bounded Measure versus Polynomial Time
Approximations...............................................87
7. NP-hard Sets Are Superterse unless NP Is Small...................91
7.1 Introduction.................................................91
7.2 Resource Bounded Measure and Polynomial Time Membership
Comparable Sets..............................................92
Bibliography..........................................................97