Category and Measure in Complexity Classes

DOI10.1137/0219076MaRDI QIDQ3495645zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219076

zbMATH Keywords

Banach-Mazur gamesexponential complexity classeshard languagesKolmogorov complexitynonuniform complexitypolynomial reducibilitiesresource-bounded categoryresource-bounded measuretime complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• A note on ``Category and measure in complexity classes
• Effective category and measure in abstract complexity theory
• Categorical complexity
• Kolmogorov complexity of categories
• Effective category and measure in abstract complexity theory
• Equivalence of measures of complexity classes
• Equivalence of Measures of Complexity Classes
• The complexity of computable categoricity
• Dimension and the structure of complexity classes
• Quantitative Relativizations of Complexity Classes

Cited in

(42)

• Resource-bounded strong dimension versus resource-bounded category
• On independent random oracles
• Almost everywhere high nonuniform complexity
• Circuit size relative to pseudorandom oracles
• The generic oracle hypothesis is false
• Almost every set in exponential time is P-bi-immune
• Genericity and measure for exponential time
• Measure on P: Strength of the notion
• Resource bounded randomness and weakly complete problems
• Resource bounded randomness and computational complexity
• Recursive computational depth.
• Weakly complete problems are not rare
• Polynomial games and determinacy
• Hard sets are hard to find
• Resource-bounded martingales and computable Dowd-type generic sets
• Feasible analysis, randomness, and base invariance
• Generic density and small span theorem
• Baire categories on small complexity classes and meager-comeager laws
• A note on dimensions of polynomial size circuits
• A note on ``Category and measure in complexity classes
• The typical constructible object
• Calibrating Randomness
• Sub-computable bounded pseudorandomness
• Genericity, Randomness, and Polynomial-Time Approximations
• scientific article; zbMATH DE number 1346358 (Why is no real title available?)
• Decomposing the complexity quotient category
• scientific article; zbMATH DE number 1500663 (Why is no real title available?)
• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• Results on resource-bounded measure
• Equivalence of measures of complexity classes
• Effective category and measure in abstract complexity theory
• Almost every set in exponential time is P-bi-immune
• Genericity and measure for exponential time (extended abstract)
• Dimension and the structure of complexity classes
• Polynomial-time axioms of choice and polynomial-time cardinality
• On the topological size of p-m-complete degrees
• Effective category and measure in abstract complexity theory
• If not empty, NP-P is topologically large
• An upward measure separation theorem
• Martingale families and dimension in P
• Resource-bounded measure on probabilistic classes
• Turing degrees of reals of positive effective packing dimension

This page was built for publication: Category and Measure in Complexity Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495645)