  In a lossless compression system with target lengths, a compressor ${\cal C}$
maps an integer $m$ and a binary string $x$ to an $m$-bit code $p$, and if $m$
is sufficiently large, a decompressor ${\cal D}$ reconstructs $x$ from $p$. We
call a pair $(m,x)$ $\textit{achievable}$ for $({\cal C},{\cal D})$ if this
reconstruction is successful. We introduce the notion of an optimal compressor
${\cal C}_\text{opt}$, by the following universality property: For any
compressor-decompressor pair $({\cal C}, {\cal D})$, there exists a
decompressor ${\cal D}'$ such that if $(m,x)$ is achievable for $({\cal
C},{\cal D})$, then $(m+\Delta, x)$ is achievable for $({\cal C}_\text{opt},
{\cal D}')$, where $\Delta$ is some small value called the overhead. We show
that there exists an optimal compressor that has only polylogarithmic overhead
and works in probabilistic polynomial time. Differently said, for any pair
$({\cal C}, {\cal D})$, no matter how slow ${\cal C}$ is, or even if ${\cal C}$
is non-computable, ${\cal C}_{\text{opt}}$ is a fixed compressor that in
polynomial time produces codes almost as short as those of ${\cal C}$. The cost
is that the corresponding decompressor is slower.
  We also show that each such optimal compressor can be used for distributed
compression, in which case it can achieve optimal compression rates, as given
in the Slepian-Wolf theorem, and even for the Kolmogorov complexity variant of
this theorem. Moreover, the overhead is logarithmic in the number of sources,
and unlike previous implementations of Slepian-Wolf coding, meaningful
compression can still be achieved if the number of sources is much larger than
the length of the compressed strings.
