Kolmogorov complexity and instance complexity of recursively enumerable sets

Martin Kummer

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 i…