Effective Category and Measure in Abstract Complexity Theory

摘要

Strong variants of the Operator Speed-up Theorem, Operator Gap Theorem andCompression Theorem are obtained using an effective version of Baire Category Theorem. It is also shown that all complexity classes of recursive predicates have effective measure zero in the space of recursive predicates and, on the other hand, the class of predicates with almost everywhere complexity above an arbitrary recursive threshold has recursive measure one in the class of recursive predicates.