Demuth randomness and computational complexity

DOI10.1016/j.apal.2011.01.004zbMath1223.03026OpenAlexW1989278258MaRDI QIDQ639659

Antonín Kučera, André Nies

Publication date: 22 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.01.004

zbMATH Keywords

highnesslownessDemuth randomnessDemuth tests

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (15)

Demuth’s Path to Randomness ⋮ CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ JSL volume 79 issue 2 Cover and Front matter ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ Randomness notions and partial relativization ⋮ STRONG JUMP-TRACEABILITY ⋮ Continuous randomness via transformations of 2-random sequences ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Inherent enumerability of strong jump-traceability ⋮ Reductions between types of numberings ⋮ Denjoy, Demuth and density

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness notions and partial relativization
• Characterizing the strongly jump-traceable sets via randomness
• Lowness properties and approximations of the jump
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Lowness properties and randomness
• A random set which only computes strongly jump-traceable c.e. sets
• Benign cost functions and lowness properties
• Randomness and Computability: Open Questions
• Every sequence is reducible to a random one
• Mass problems and almost everywhere domination
• Using random sets as oracles
• Computability and Randomness
• ∏ 0 1 Classes and Degrees of Theories
• Randomness, relativization and Turing degrees

This page was built for publication: Demuth randomness and computational complexity