Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

DOI10.1137/S0097539794268789MaRDI QIDQ5691287zbMATH OpenOpenAlexFDO

Authors

Publication date 28 January 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9405208

zbMATH Keywords

complete setinitial segmentsinstance complexityKolmogorov complexityrecursively enumerable setsTuring degrees

Mathematics Subject Classification ID

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

Abstract: We study in which way Kolmogorov complexity and instance complexity affect properties of r.e. sets. We show that the well-known 2log n upper bound on the Kolmogorov complexity of initial segments of r.e. sets is optimal and characterize the T-degrees of r.e. sets which attain this bound. The main part of the paper is concerned with instance complexity of r.e. sets. We construct a nonrecursive r.e. set with instance complexity logarithmic in the Kolmogorov complexity. This refutes a conjecture of Ko, Orponen, Sch"oning, and Watanabe. In the other extreme, we show that all wtt-complete set and all Q-complete sets have infinitely many hard instances.

Recommendations

• On resource-bounded instance complexity
• Kolmogorov complexity and computably enumerable sets
• Random strings make hard instances
• Instance complexity

Cited in

(33)

• Dynamic notions of genericity and array noncomputability
• On resource-bounded instance complexity
• Randomness and reducibility
• Time-bounded Kolmogorov complexity and Solovay functions
• The complexity of irredundant sets parameterized by size
• \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets
• Integer valued betting strategies and Turing degrees
• Fixed-parameter decidability: extending parameterized complexity analysis
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• scientific article; zbMATH DE number 3847369 (Why is no real title available?)
• Calibrating Randomness
• Degrees of monotone complexity
• TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
• scientific article; zbMATH DE number 1138314 (Why is no real title available?)
• 1999–2000 Winter Meeting of the Association for Symbolic Logic
• Avoiding effective packing dimension 1 below array noncomputable c.e. degrees
• A hierarchy of computably enumerable degrees
• 2003 Annual Meeting of the Association for Symbolic Logic
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• Kolmogorov complexity and computably enumerable sets
• Trivial Reals
• Working with strong reducibilities above totally -c.e. and array computable degrees
• Kobayashi compressibility
• scientific article; zbMATH DE number 2196513 (Why is no real title available?)
• Maximality and collapse in the hierarchy of -c.a. degrees
• Complexity properties of recursively enumerable sets and bsQ-completeness
• Irreducible, singular, and contiguous degrees
• Regainingly approximable numbers and sets
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• Compression of enumerations and gain
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Turing degrees of reals of positive effective packing dimension
• Time-bounded incompressibility of compressible strings and sequences

This page was built for publication: Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets

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