Let us $ \Sigma = \{0,1\}$ and $ f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $ \exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \rvert ^ k$ . Thus, we can say that the function $ f$ is *one-way function*.

We have language $ L = \{ w \; | \; \exists z \in \Sigma^*, w = f(z)\}$ . The question is, how to prove that $ f$ is not *injective* if $ L \in NP \setminus UP$ , where $ UP$ is the class of unambiguous TM.

It is clear, that if $ L \in NP \setminus UP$ then exists NTM which decides this language and may exist at least one acceptable path for $ w \in L$ .