Degrees of monotone complexity

DOI10.2178/jsl/1164060458zbMath1109.03033MaRDI QIDQ3416117

William C. Calhoun

Publication date: 19 January 2007

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.576.302

zbMATH Keywords

monotone complexity; computably enumerable reals; monotone degree; relative randomness of reals

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

03D25: Recursively (computably) enumerable sets and degrees

Related Items

On the computational power of random strings, Increasing the gap between descriptional complexity and algorithmic probability

Cites Work

• Unnamed Item
• Program size complexity for possibly infinite computations
• Process complexity and effective random tests
• The recursively enumerable degrees are dense
• Lowness properties and randomness
• Randomness, Computability, and Density
• Algorithmic Randomness and Complexity
• A Theory of Program Size Formally Identical to Information Theory
• Relations between varieties of kolmogorov complexities
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• A variant of the Kolmogorov concept of complexity
• A formal theory of inductive inference. Part II
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets