Genericity and Measure for Exponential Time
Klaus Ambos-Spies, Hans-Christian Neis, Sebastiaan A. Terwijn

Abstract:
Recently Lutz introduced a polynomial time bounded version of Lebesgue
measure. He and others used this concept to investigate the quantitative 
structure of Exponential Time (E=DTIME(2^lin)). Previously, Ambos­Spies, 
Fleischhack and Huwig introduced polynomial time bounded genericity 
concepts and used them for the investigation of structural properties of 
NP (under appropriate assumptions) and E. Here we relate these concepts 
to each other. We show that, for any c>=1, the class of n^c­generic sets 
has p­measure 1. This allows us to simplify and extend certain 
p­measure 1­results. To illustrate the power of generic sets we take the 
Small Span Theorem of Juedes and Lutz  as an example and prove a 
generalization for bounded query reductions.