Kolmogorov complexity and non-determinism

AbstractWe are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs, (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set