3 ms·
The existence of one-way functions is also equivalent to P != NP: https://forwardscattering.org/post/33 https://forwardscattering.org/post/33
by Ono-Sendai 5y ago
The existence of one-way functions is also equivalent to P != NP: https://forwardscattering.org/post/33 https://forwardscattering.org/post/33
- throwaway81523 5y agoI think this is more like Impagliazzo's "Pessiland", where P!=NP but cryptography is still impossible.
- isaacg 5y agoThat's not exactly what the page you linked says. The existence of one-way functions implies P != NP, but the reverse is not known to be true. In particular, it's possible that P != NP, but also no one-way-functions exist. See Impagliazzo's Five Worlds for more: http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html?m=1 http://blog.computationalcomplexity.org/2004/06/impagliazzos... All five worlds are still possible, given our current results. In both "Heuristica" and "Pessiland", P != NP but one-way-functions do not exist.
- Vervious 5y agoyeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.
- joe_the_user 5y agoI haven't looked at this blog post in detail but the claim seems unlikely. Broadly, P!=NP is about worst case scenarios and the existence of one-way functions is about average case scenarios. If a few paragraphs could prove a relationship between the two, it would be a remarkable result indeed.