Complexity and randomness

MaRDI QIDQ3418262zbMATH OpenFDO

Authors Sebastiaan A. Terwijn

Publication date 2 February 2007

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other Turing degree structures (03D28) Complexity of computation (including implicit computational complexity) (03D15) Applications of computability and recursion theory (03D80) Other connections with logic and set theory (28E15)

Recommendations

• Around Kolmogorov complexity: basic notions and results
• Algorithmic randomness and complexity.
• Algorithmic randomness and measures of complexity
• The Kolmogorov complexity of random reals
• Kolmogorov Complexity and Algorithmic Randomness

Cited in

(13)

• The Medvedev lattice of computably closed sets
• Complexity of generation
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• Randomness – A Computational Complexity Perspective
• Algorithmic randomness and complexity.
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• On partial randomness
• On the Hausdorff dimension of maximal chains and antichains of Turing and hyperarithmetic degrees
• scientific article; zbMATH DE number 7215284 (Why is no real title available?)
• Fractal dimension versus process complexity
• Exact constructive and computable dimensions
• Strong jump-traceability. II: K-triviality
• Five lectures on algorithmic randomness

This page was built for publication: Complexity and randomness

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