Relations between varieties of Kolmogorov complexities

There are several sorts of Kolmogorov complexity, better to say several Kolmogorov complexities: decision complexity, simple complexity, prefix complexity, monotonic complexity, a priori complexity. The last three can and the first two cannot be used for defining randomness of an infinite binary sequence. All those five versions of Kolmogorov complexity were considered, from a unified point of view, in a paper by the first author which appeared in Watanabe's book [23]. Upper and lower bounds for those complexities and also for their differences were announced in that paper without proofs. (Some of those bounds are mentioned in Section 4.4.5 of [16].) The purpose of this paper (which can be read independently of [23]) is to give proofs for the bounds from [23]. The terminology used in this paper is somehow nonstandard: we call ''Kolmogorov entropy'' what is usually called ''Kolmogorov complexity.'' This is a Moscow tradition suggested by Kolmogorov himself. By this tradition the term ''complexity'' relates to any mode of description and ''entropy'' is the complexity related to an optimal mode (i.e., to a mode that, roughly speaking, gives the shortest descriptions).