Hacker News new | ask | show | jobs
by aleph_minus_one 494 days ago
> It's not known even in theory whether P != NP implies that one-way functions exist: for example, it might be that all NP problems are easy on average, or that there are problems that are hard on average but that you can't sample the problems and their solution at the same time.

Relevant paper:

Impagliazzo, R. A personal view of average-case complexity theory. In Proceedings of the 10th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press (1995), 134–147.

https://ieeexplore.ieee.org/document/514853

Non-paywall links:

- https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf

- https://gwern.net/doc/cs/cryptography/1995-impagliazzo.pdf

Popular scientific articles on this topic:

- https://www.quantamagazine.org/which-computational-universe-...

- https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the...