47 Pages

Resource-Bounded Measure and Randomness

WithKlaus Ambos-Spies, Elvira Mayordomo

We survey recent results on resource-bounded measure and randomness in structural complexity theory. In particular, we discuss applications of these concepts to the exponential time complexity classes E and E 2. Moreover, we treat time-bounded genericity and stochasticity concepts which are weaker than time-bounded randomness but which suffice for many of the applications in complexity theory.