1
$\begingroup$

By definition:

A polynomial-time computable function $f:$ $\{$0,1$\}$$^*$→ $\{$0,1$\}$$^*$ is a one-way function if for every probabilistic polynomial time Turing Machine $PTM$ there is a neglegibible function $E$ $:$$\mathbb{N} → \mathbb{N} $ $ \ s.t. \ $ $Pr$ $x$ $∈$ $\{$0,1$\}$$^n$ $[PTM \ \ inverts \ \ f(x)] ≤ E(n)$.

Now, reading the definition above, the existence of one-way functions seems like an easy bet, however it is considered a stronger assumption than $P \neq NP$. Apparently proving the existence of these functions would be more difficult than proving $P = NP ?$ And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

What steps would a mathematician or computer scientist take to prove that one-way functions exist? I believe that since proving its existence would also prove $P \neq NP$, this means that we cannot use the techniques that we know for sure does not work: Relativization, diagonalization, Natural Proof.

So, what form could such a proof take? Maybe something in second(+)-order logic?

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not sure how this is a better question than asking what a $\mathsf{P} \neq \mathsf{NP}$ proof would look like. Perhaps the question is better poised as "what form could such a proof not take (in addition to relativization techniques, etc.)?" $\endgroup$
    – dkaeae
    Commented Jul 15, 2019 at 7:37
  • $\begingroup$ This question should scrap all mention of P≠NP (which is separate question) and simply focus on why it's hard to prove one-way functions exist. $\endgroup$
    – Geremia
    Commented Sep 16, 2023 at 16:55

1 Answer 1

Reset to default
1
$\begingroup$

Apparently proving the existence of these functions would be more difficult than proving $P\not =NP$? And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

The answer is in your question itself:

I believe that since proving its existence would also prove $P\not =NP$

This is indeed the case. Somebody that proves the existence of one-way functions automatically also proves $P\not = NP$. On the other hand, it is conceivable that you could prove $P\not = NP$ without proving that one way functions exist. Thus, proving the existence of one-way functions is at least as hard as proving $P\not = NP$.

What steps would a mathematician or computer scientist take to prove that one-way functions exist?

Coming up with an extremely clever and creative idea that nobody came up with before.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "The answer is in your question itself[:] 'I believe that since proving its existence would also prove P≠NP'" You're asked "Why is it difficult to prove the existence of one-way functions?" and you 'answer' "Because I assume P≠NP." $\endgroup$
    – Geremia
    Commented Sep 16, 2023 at 16:53
  • $\begingroup$ @Geremia No, that's not what my answer is. My "assumption" is that settling the P v.s. NP question is hard (since a lot of people have tried and nobody has managed). Now if you believe that settling P v.s. NP (either way) is hard, then proving that one-way functions exist must also be hard: if you managed to do so you'd also prove that P≠NP, but it is not impossible that P≠NP but no one-way functions exist. Therefore proving that one-way functions exist is a "strictly harder" task than proving that P≠NP. $\endgroup$
    – Tom van der Zanden
    Commented Sep 17, 2023 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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