Store a n-bit string using only O(log n) space 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.
There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.