1
$\begingroup$

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two strings $s_1,s_2$ have length $2^n$ and $\forall i\in\{1,\cdots,n^c\}, \; f_i(s_j)\leq n^d, \; j\in \{1,2\}$?

It seems a little similar to hash functions but since we don't have any restrictions (e.g. having uniform distribution or being oneway) our hands are open to define whatever we like.

I think it's not possible. Because we have $2^{2^n}$ strings of size $2^n$ and transformring them into polynomial size strings means we have put many strings in a single string. But when I make an example this comes to my mind that maybe by defining a good design for each function we can recognize the difference by probability one.

One example can be:

For $c=3$ and $d=1$,

$f_1$: it takes string of length $2^n$ and transforms it to $mod\, n$.

$f_2$: it takes string of length $2^n$. (suppose we have divided $2^{2^n}$ strings into $\frac{2^{2^n}}{n}$ collections) If the input belongs to $i$th collection, $f_2$ transforms it to $i$.

$f_3$: it takes string of length $2^n$ and transforms it to the number which shows its $1$s number.

The probability that for two strings $s_1$ and $s_2$, these three maps $f_1, f_2,f_3$ be the same would be $$\frac{1}{n}\times \frac{1}{n} \times \frac{1}{2^{2n}}$$ That is negligible.

So my question is that can we ever understand the difference of two long strings with probability $1$ using polynomial size strings?

$\endgroup$
2
$\begingroup$

There is no sequence of functions $f_1,...,f_{n^c}:\{0,1\}^{2^n}\rightarrow\{0,1\}^{n^d}$, such that for all $s_1\neq s_2\in\{0,1\}^{2^n}$ $\exists i\in\{1,...,n^c\} : f_1(s_1)\neq f_i(s_2)$.

Examine the function $F:\{0,1\}^{2^n}\rightarrow \prod\limits_{i=1}^{n^c}\{0,1\}^{n^d}$ defined by $F(s)=\left(f_1(s),f_2(s),...,f_{n^c}(s)\right)$.

The domain of $F$ is of cardinality $2^{2^n}$, while its range is of cardinality $\left(2^{n^d}\right)^{n^c}=2^{n^{c+d}}$. Since for large enough $n$ it holds that $2^{2^n}>2^{n^{c+d}}$, $F$ is not one to one, and thus the condition is not satisfied.

$\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.