Duration:
-
Abstract:
New extensions of Lebesgue measure theory are used to investigate the internal, quantitative structure of complexity classes. The relationships among intrinsically pseudorandom objects, pseudorandom number generators, probabilistic and interactive complexity classes, and completeness phenomena are studied. Another focus is the measure structure of exponential time complexity classes.
Funding Organization
The Internal Quantitative Structure of Complexity Classes
Award Amount
$266,000
Award Number
9157382