Kolmogorov complexity and instance complexity of recursively enumerable sets

Details Kolmogorov complexity and instance complexity of recursively enumerable sets Kolmogorov complexity and instance complexity of recursively enumerable sets

1994-05-25

arxiv.org/abs/math/9405208v1

Mathematics

Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov complexity and instance complexity of recursively enumerable sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kolmogorov complexity and instance complexity of recursively enumerable sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexity and instance complexity of recursively enumerable sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-566427