Degrees of monotone complexity

DOI10.2178/JSL/1164060458MaRDI QIDQ3416117zbMATH OpenOpenAlexFDO

Authors 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 complexitycomputably enumerable realsmonotone degreerelative randomness of reals

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 176869
• Complexity of monotonic functions
• Triviality and minimality in the degrees of monotone complexity
• Monotone complexity of a pair
• On the mean complexity of monotone functions
• scientific article; zbMATH DE number 910751
• scientific article; zbMATH DE number 5242388
• Complexity results related to monophonic convexity
• The complexity of monotone computations of polynomials
• Monotone measures of statistical complexity

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part II
• A variant of the Kolmogorov concept of complexity
• Algorithmic randomness and complexity.
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Lowness properties and randomness
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• Process complexity and effective random tests
• Program size complexity for possibly infinite computations
• Randomness, computability, and density
• Relations between varieties of kolmogorov complexities
• The recursively enumerable degrees are dense

Cited in

(7)

• Triviality and minimality in the degrees of monotone complexity
• On the computational power of random strings
• Complexity of monotonic functions
• Increasing the gap between descriptional complexity and algorithmic probability
• Monotone complexity of a pair
• Monotone measures of statistical complexity
• scientific article; zbMATH DE number 841094 (Why is no real title available?)

This page was built for publication: Degrees of monotone complexity

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