Search

PYI: The Internal Quantitative Structure of Complexity Classes

Project

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.


 

Category: 
Grants
Tags: 
PI: Jack Lutz

Pages