1
$\begingroup$

Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.

$\endgroup$
  • 1
    $\begingroup$ You can store all the information in the universe in just one bit. In particular you can store a string of any size. A different question is how many different strings could be stored in the same space. $\endgroup$ – plop Nov 27 '20 at 14:39
4
$\begingroup$

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.

$\endgroup$
1
$\begingroup$

When you say "store", I suppose you're also expecting to be able to retrieve the original string based on the shorter string, right?

If so, then the answer is a categorical no. And not only to log(n), but even to n-1.

Theorem: it is not possible to construct a program that reversibly converts all possible strings of length n to strings of length m, where m<n.

Proof by contradiction: let's suppose there was a program that could reversibly convert all strings of size n, to strings of size m. There are 2^n inputs, and 2^m outputs, where 2^n < 2^m. But in order to revert the conversion, there must be at least two outputs that revert to the same input, therefore the conversion is not reversible.

This proof is another way of explaining the pigeonhole principle: you cannot put 10 pigeons in 9 pigeonholes, without using at least one of the pigeonholes at least twice.

A lot of people seem to be surprised by this. Isn't storing data in a smaller size the entire point of lossless compression? Compressors are based on finding patterns that can be stored with less data, but ultimately, the same theorem proves that it is not possible to create a program that can losslessly compress all possible inputs to a smaller size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.