Compression of enumerations and gain
This addresses theoretical problems in computational complexity and algorithmic information theory, with incremental contributions to understanding enumeration compression.
The paper investigates the compressibility of enumerations in Kolmogorov complexity, showing that strong compression and weak gainless compression exist for any computably enumerable set, and reduces the density problem to the question of well-compressibility via enumeration games.
We study the compressibility of enumerations in the context of Kolmogorov complexity, focusing on strong and weak forms of compression and their gain: the amount of auxiliary information embedded in the compressed enumeration. The existence of strong compression and weak gainless compression is shown for any computably enumerable (c.e.) set. The density problem of c.e. sets with respect to their prefix complexity is reduced to the question of whether every c.e. set is well-compressible, which we study via enumeration games.