Timeline for Difficulty in proving the existence of one-way functions
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17, 2023 at 6:37 | comment | added | Tom van der Zanden | @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. | |
| Sep 16, 2023 at 16:53 | comment | added | Geremia | "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." | |
| Jul 15, 2019 at 9:16 | history | answered | Tom van der Zanden | CC BY-SA 4.0 |