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, AmbosSpies,
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^cgeneric sets
has pmeasure 1. This allows us to simplify and extend certain
pmeasure 1results. 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.