Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
From MaRDI portal
Publication:5691287
DOI10.1137/S0097539794268789zbMath0859.03015arXivmath/9405208OpenAlexW2035556343MaRDI QIDQ5691287
No author found.
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
Kolmogorov complexitycomplete setrecursively enumerable setsTuring degreesinstance complexityinitial segments
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25)
Related Items
Randomness and reducibility ⋮ On resource-bounded instance complexity ⋮ Time-Bounded Kolmogorov Complexity and Solovay Functions ⋮ AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Irreducible, singular, and contiguous degrees ⋮ Trivial Reals ⋮ Kobayashi compressibility ⋮ Turing degrees of reals of positive effective packing dimension ⋮ 2003 Annual Meeting of the Association for Symbolic Logic ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Time-bounded incompressibility of compressible strings and sequences ⋮ A uniform version of non-\(\mathrm{low}_{2}\)-ness ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Calibrating Randomness ⋮ Degrees of monotone complexity ⋮ Dynamic notions of genericity and array noncomputability ⋮ Maximality and collapse in the hierarchy of α-c.a. degrees ⋮ 1999–2000 Winter Meeting of the Association for Symbolic Logic ⋮ \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets ⋮ Integer valued betting strategies and Turing degrees
