Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That'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... All five worlds are still possible, given our current results. In both "Heuristica" and "Pessiland", P != NP but one-way-functions do not exist.



yeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: