scientific article; zbMATH DE number 969633

MaRDI QIDQ5284998zbMATH OpenFDO

Authors Y. Wang

Publication date 22 January 1997

zbMATH Keywords

computational complexitylaw of the iterated logarithmapproximationsrandomness\(n\)-randomnessintractable setsresource bounded randomness\(p\)-random sequencesresource bounded random sequences

Mathematics Subject Classification ID

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

Recommendations

• Complexity and randomness
• scientific article; zbMATH DE number 4089442
• scientific article; zbMATH DE number 7377983
• Randomness and computation
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
• Randomness -- a computational complexity perspective
• Randomness – A Computational Complexity Perspective
• Algorithmic randomness and measures of complexity
• Randomness and hyper-randomness
• scientific article; zbMATH DE number 739156

Cited in

(30)

• Hierarchy of Computably Enumerable Degrees II
• Process and truth-table characterisations of randomness
• Schnorr randomness
• Polynomial clone reducibility
• The smallest probability interval a sequence is random for: a study for six types of randomness
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Genericity, Randomness, and Polynomial-Time Approximations
• Some Questions in Computable Mathematics
• Comparing notions of randomness
• Constructive equivalence relations on computable probability measures
• Dimension and the structure of complexity classes
• NP-hard sets are superterse unless NP is small
• On Kurtz randomness
• Recursive computational depth.
• Recursive computational depth
• On generalized computable universal priors and their convergence
• A separation of two randomness concepts
• A hierarchy of computably enumerable degrees
• Randomness – A Computational Complexity Perspective
• Resource bounded randomness and computational complexity
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• Resource-bounded balanced genericity, stochasticity and weak randomness
• Intermediate intrinsic density and randomness
• Feasible analysis, randomness, and base invariance
• Randomness is inherently imprecise
• Degrees of sets having no subsets of higher m- and t t-degree
• Effective randomness for computable probability measures
• Difference randomness
• Closure of resource-bounded randomness notions under polynomial-time permutations
• Kobayashi compressibility

This page was built for publication:

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