Category and Measure in Complexity Classes
From MaRDI portal
Publication:3495645
DOI10.1137/0219076zbMath0711.68046OpenAlexW2077218542MaRDI QIDQ3495645
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
Kolmogorov complexitytime complexitypolynomial reducibilitiesnonuniform complexityresource-bounded measureresource-bounded categoryBanach-Mazur gamesexponential complexity classeshard languages
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A note on ``Category and measure in complexity classes, Sub-computable Bounded Pseudorandomness, Almost every set in exponential time is P-bi-immune, Genericity and measure for exponential time, The Typical Constructible Object, Measure on \(P\): Strength of the notion, Results on resource-bounded measure, Weakly complete problems are not rare, Polynomial games and determinacy, Functions that preserve p-randomness, Resource bounded randomness and weakly complete problems, Dimension and the structure of complexity classes, Polynomial-time axioms of choice and polynomial-time cardinality, Hard sets are hard to find, Martingale families and dimension in P, On independent random oracles, On the topological size of p-m-complete degrees, Effective category and measure in abstract complexity theory, Almost everywhere high nonuniform complexity, Generic density and small span theorem, Baire categories on small complexity classes and meager-comeager laws, If not empty, NP-P is topologically large, Resource-bounded measure on probabilistic classes, Circuit size relative to pseudorandom oracles, The generic oracle hypothesis is false, Effective category and measure in abstract complexity theory, Turing degrees of reals of positive effective packing dimension, A note on dimensions of polynomial size circuits, Almost every set in exponential time is P-bi-immune, Genericity and measure for exponential time, Resource bounded randomness and computational complexity, Calibrating Randomness, Genericity, Randomness, and Polynomial-Time Approximations, Resource-bounded strong dimension versus resource-bounded category, Recursive computational depth., Resource-bounded martingales and computable Dowd-type generic sets, An upward measure separation theorem, Feasible analysis, randomness, and base invariance
