scientific article; zbMATH DE number 969633

MaRDI QIDQ5284998zbMATH OpenFDO

Authors Y. Wang

Publication date 22 January 1997

zbMATH Keywords

\(n\)-randomness\(p\)-random sequencesapproximationscomputational complexityintractable setslaw of the iterated logarithmrandomnessresource bounded random sequencesresource bounded randomness

Mathematics Subject Classification ID

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

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

(39)

• Constructive equivalence relations on computable probability measures
• Resource bounded randomness and computational complexity
• Randomness, stochasticity, and approximations
• Recursive computational depth.
• On Kurtz randomness
• Randomness is inherently imprecise
• The smallest probability interval a sequence is random for: a study for six types of randomness
• Feasible analysis, randomness, and base invariance
• Polynomial clone reducibility
• NP-hard sets are superterse unless NP is small
• A separation of two randomness concepts
• Some Questions in Computable Mathematics
• Difference randomness
• Closure of resource-bounded randomness notions under polynomial-time permutations
• Hierarchy of Computably Enumerable Degrees II
• Randomness – A Computational Complexity Perspective
• Genericity, Randomness, and Polynomial-Time Approximations
• Recursive computational depth
• Resource-bounded balanced genericity, stochasticity and weak randomness
• A hierarchy of computably enumerable degrees
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• Schnorr randomness
• Effective randomness for computable probability measures
• Intermediate intrinsic density and randomness
• Kobayashi compressibility
• Degrees of sets having no subsets of higher m- and t t-degree
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Dimension and the structure of complexity classes
• A comparative study of the smallest probability intervals for which a binary sequence is random
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Algorithmically random series
• Process and truth-table characterisations of randomness
• Algorithmic randomness in continuous-time Markov chains
• Comparing notions of randomness
• On generalized computable universal priors and their convergence

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)