This is page Printer Opaque this The Quantitative Structure of Exponential Time

ABSTRACT Recent results on the internal measuretheoretic structure of the exponential time complexity classes E and EXP are surveyed The mea sure structure of these classes is seen to interact in informative ways with biimmunity complexity cores polynomialtime reductions completeness circuitsize complexity Kolmogorov complexity natural proofs pseudoran dom generators the density of hard languages randomized complexity and lowness Possible implications for the structure of NP are also discussed In the past ve years new developments in resourcebounded measure have opened the way for a systematic investigation of the internal measure theoretic structure of the exponential time complexity classes E and EXP The investigation is very far from complete but it has already yielded