##### The times they are a-changin’.

This post seems to be older than 13 years—a long time on the internet. It might be outdated.

Alright team, let’s get cracking:

From www.kottke.org:

Another Wikipedia gem: a list of unsolved problems from a number of different fields, including linguistics, physics, and computer science. (via lone gunman)

I think my favorite problem deals with the existence of one-way functions, also called hash functions^{1}:

From en.wikipedia.org:

**Description**

One-way functions are easy to compute but hard to invert. Although there are several candidates for which no good (i.e. quick) reverse algorithms are currently known, it hasn’t yet been proven that any function exists for which no such reverse algorithms exist.

**Importance**

If one-way functions do not exist then public key cryptography is impossible. Their existence would imply that many complexity classes are not learnable, and that Pâ‰ NP.

**Conjecture**

It is assumed but unproven that they do exist. Several encryption systems are based on the assumption that modular exponentiation is a one-way function.

^{1} Kind of. Hash functions usually return a value of fixed length, which precludes them from being true one-way functions.

0

*Related*