Natural Examples of Simple and Hypersimple Sets.
by
Alexei Semenov
Institute of New Technologies, Moscow
Coauthors: Andrej Muchnik

Andrey Andreevich Markov remarked that there are two approaches to measuring complexity of algorithms: the computational and the descriptive ones. Within both frameworks different refinements are possible. For computational complexity, there are such measures as time and space. For descriptive complexity, we can consider the length of the shortest program in a certain optimal language or in a certain optimal prefix language. (A programming language is called prefix if no program can be a beginning of any other program.) A prefix language allows us to storage compactly not only separate programs, but collections of them.

Denote by KS(x) the length of the shortest program that generates x from the empty input, and by KP(x) the length of the prefix program with the same property. If a computable function f is less than KS (or KP) everywhere, then f is bounded. Thus a computable lower bound of KS (or KP) cannot be sharp on an infinite set. There exist computable upper bounds of KS and KP that are sharp on an infinite set. The complements of those sets are simple in terms of Post. For KP, those sets are even hypersimple (for KS, this can be wrong). We used some results of G. Marandzhyan and R. Solovay.

Date received: April 19, 2003