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

  • $\begingroup$ Isn't L being in UP the same as $f$ being injective? $\endgroup$ – Peter Shor May 2 '20 at 12:07
  • $\begingroup$ Yes, it is. How I have written, when $L \in NP \setminus UP$ then $f$ cannot be injective, because there can exist at least one acceptable path in the NTM. But, maybe I want some idea about how to prove this way in more formally. $\endgroup$ – Peter Hofschatter May 2 '20 at 12:11
  • $\begingroup$ You cannot say that $f$ is a one-way function. One-way functions have a definition, which is very far from what you wrote. $\endgroup$ – Yuval Filmus May 2 '20 at 12:53
  • $\begingroup$ If we do not consider the condition to the inverse function $f^{-1}$, then we could say that it is a one-way function. I was inaccurate in the question, you're right. $\endgroup$ – Peter Hofschatter May 2 '20 at 13:00

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.

Since $L$ is always in $\mathsf{NP}$ (using the very same machine), the contrapositive is exactly the statement you're after.


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.